Floor Div Convolution?

2 secs 1024 MB

ecottea

Problem

Submissions

Test cases

Editorial

解説

便宜上，整数列 $A, B$ の範囲外の値を全て $0$ とします．和の範囲を定める条件 $\lfloor \frac{i}{j} \rfloor = k$ は

j k \leq i \lt j (k + 1)

と同値なので， $k \geq 1$ に対する $C_k$ は

C_k = \sum_{j=1}^{\lfloor N/k \rfloor} B_j \sum_{i = j k}^{j (k + 1) - 1} A_i

と書き直せます． $A$ の累積和を $O(M)$ で前計算しておけば，この式に従って各 $k = 1, 2, \ldots, N$ に対する $C_k$ をそれぞれ $O(\frac{N}{k})$ で計算することができます． $k = 0$ のときは

C_0 = \sum_{j=1}^{M} B_j \sum_{i = 0}^{j - 1} A_i

となり，こちらも $A$ の累積和を用いれば $O(M)$ で計算できます．全体の計算量は $O(M + N \log N)$ となり本問の制約下で十分高速です．

想定解（C++）

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
constexpr ll MOD = 998244353;
​
int main() {
    int n, m;
    cin >> n >> m;
​
    vector<ll> a(n + 1), b(m + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int j = 1; j <= m; j++) cin >> b[j];
​
    vector<ll> acc(n + 2);
    for (int i = 1; i <= n; i++) acc[i + 1] = (acc[i] + a[i]) % MOD;
​
    vector<ll> c(n + 1);
    for (int j = 1; j <= m; j++) {
        c[0] = (c[0] + b[j] * acc[min(j, n + 1)]) % MOD;
    }
    for (int k = 1; k <= n; k++) {
        for (int j = 1; j <= min(m, n / k); j++) {
            c[k] = (c[k] + b[j] * (acc[min(j * (k + 1), n + 1)] - acc[j * k])) % MOD;           
        }
        if (c[k] < 0) c[k] += MOD;
    }
​
    for (int k = 0; k <= n; k++) {
        cout << c[k] << " \n"[k == n];
    }
}
​