Dec 15, 2019 由 小羊
我不会狄利克雷卷积。输得彻底。
给出一个很直观的解法代码。
前提是理解好 时 。
那么
首先显然 ,假设已经求出 里的所有值,以及可能取到的上标 ,那么就可以得到 。我们可以从小往大递推 ,然后求得 后得到 ,并解出 以方便后续计算。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int mod = 998244353;
int g[maxn], f[maxn][64], b[maxn][64];
vector<int> d[maxn];
int n, k, kk[64], invk, tok;
int fpow(long long a, int k) {
long long b = 1;
for (; k; k >>= 1, a = a * a % mod)
if (k & 1) b = b * a % mod;
return b;
}
int main()
{
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &g[i]);
for (int i = 2; i <= n; i++)
for (int j = i+i; j <= n; j += i)
d[j].push_back(i);
for (int tmp = k; tmp; ) {
kk[++tok] = tmp;
if (tmp % 2 == 1) tmp--; else tmp /= 2;
} // the used ks
invk = fpow(k, mod-2);
// find for each f(n)
for (int i = 1; i <= tok; i++) f[1][i] = 1;
for (int i = 2; i <= n; i++)
{
// if we know about f[1..n-1], let f[n] = x
// so it can be proved that fk[n] = kx+b
for (int j = tok-1; j; j--)
{
long long tmp = b[i][j+1];
if (!(kk[j] & 1)) tmp <<= 1;
int sec = (kk[j] & 1) ? tok : j+1;
for (auto dd : d[i])
tmp += 1ll * f[dd][j+1] * f[i/dd][sec] % mod;
b[i][j] = tmp % mod;
}
// now we have g[n] = Kx+b, just...
f[i][tok] = 1ll * (g[i] - b[i][1] + mod) * invk % mod;
for (int j = tok-1; j; j--)
f[i][j] = (1ll * kk[j] * f[i][tok] + b[i][j]) % mod;
assert(f[i][1] == g[i]);
}
for (int i = 1; i <= n; i++)
printf("%d ", f[i][tok]);
return 0;
}
复杂度为 。
另外给出一个道听途说的做法,当时完全没有想到的。
如果你手算能力够强,那么可以发现 是个类似于求和的东西,结果对 敏感,如果令 ,那么求和结果为 ,对 卷 次也可以得到 。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int mod = 998244353;
int g[maxn], f[maxn], n;
int fpow(long long a, int k) {
long long b = 1;
for (; k; k >>= 1, a = a * a % mod)
if (k & 1) b = b * a % mod;
return b;
}
void conv(int a[maxn], const int b[maxn]) {
static int c[maxn];
fill(c, c+n+1, 0);
for (int i = 1; i <= n; i++)
for (int j = 1; j * i <= n; j++)
c[j*i] = (c[j*i] + 1ll * a[i] * b[j]) % mod;
copy(c, c+n+1, a);
}
int main()
{
int k; scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &g[i]);
k = fpow(k, mod-2); f[1] = 1;
for (; k; k >>= 1, conv(g, g))
if (k & 1) conv(f, g);
for (int i = 1; i <= n; i++)
printf("%d ", f[i]);
return 0;
}
不太会证明,能AC,复杂度为 。