LibreOJ 6713 「EC Final 2019」狄利克雷 k 次根 加强版

发表于 | 分类于 | 18

狄利克雷生成函数也是生成函数啊（

对于数论函数 f，有狄利克雷生成函数 F(s)=∞∑n=1f(n)ns

注意到狄利克雷生成函数的卷积相当于数论函数的狄利克雷卷积，于是便是要求 Fk(x)=G(x)。
由于 F′(s)=∞∑n=1f(n)lnnns，设 f′(n)=f(n)lnn。

有 Fk(s)=G(s)[Fk(s)]′=G′(s)kFk−1(s)F′(s)=G′(s)kF′(s)G(s)F−1(s)=G′(s)F′(s)G(s)=1kF(s)G′(s)∑d|nf′(d)g(nd)=1k∑d|nf(d)g′(nd)f′(n)+∑d|n∧d<nf′(d)g(nd)=1k∑d|n∧d<nf(d)g′(nd)

考虑从 f(1) 开始递推即可。

然而我并没有写这个做法，而是使用了直接 ln/exp 的通解（
众所周知
lnF(s)=∫s0F′(x)F(x)dx

F(s) 的积分就每一项乘 ln−1n，因为是常数。
除法使用狄利克雷除法，通俗地说就是逆向狄利克雷卷积（可见代码）。

exp 的话，求导之后从 f(1)=1 狄利克雷卷积递推求 f′(n)，然后积分即可。

然而发现一个问题。
模意义下哪来 lnn（
但是它毕竟是一个常数，那么注意到满足积的求导法则，即满足完全加性就不会出锅。
于是用质因子个数函数代替即可。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <cstring>
#define add(x,y) (x + y >= (mod - 1) ? x + y - (mod - 1) : x + y)
#define dec(x,y) (x < y ? x - y + (mod - 1) : x - y)
using namespace std;
const int N = 1e6;
const int mod = 998244353;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int n,k;
int f[N + 5],g[N + 5];
int vis[N + 5],cnt,prime[N + 5],c[N + 5];
int inv[25];
void ln(int *f,int n)
{
    for(register int i = 1;i <= n;++i)
        g[i] = (long long)f[i] * c[i] % mod;
    for(register int i = 1;i <= n;++i)
    {
        for(register int j = 2;i * j <= n;++j)
            g[i * j] = (g[i * j] - (long long)g[i] * f[j] % mod + mod) % mod;
        i > 1 && (g[i] = (long long)g[i] * inv[c[i]] % mod);
    }
    for(register int i = 1;i <= n;++i)
        f[i] = g[i];
}
void exp(int *f,int n)
{
    memset(g + 1,0,sizeof(int) * n),g[1] = 1;
    for(register int i = 1;i <= n;++i)
        f[i] = (long long)f[i] * c[i] % mod;
    for(register int i = 1;i <= n;++i)
    {
        i > 1 && (g[i] = (long long)g[i] * inv[c[i]] % mod);
        for(register int j = 2;i * j <= n;++j)
            g[i * j] = (g[i * j] + (long long)g[i] * f[j]) % mod;
    }
    for(register int i = 1;i <= n;++i)
        f[i] = g[i];
}
int main()
{
    scanf("%d%d",&n,&k),k = fpow(k,mod - 2);
    for(register int i = 2;i <= n;++i)
    {
        if(!vis[i])
            c[prime[++cnt] = i] = 1;
        for(register int j = 1;j <= cnt && i * prime[j] <= n;++j)
        {
            vis[i * prime[j]] = 1,c[i * prime[j]] = c[i] + 1;
            if(!(i % prime[j]))
                break;
        }
        ans = ans < c[i] ? c[i] : ans;
    }
    inv[1] = 1;
    for(register int i = 2;i <= 20;++i)
        inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
    for(register int i = 1;i <= n;++i)
        scanf("%d",f + i);
    ln(f,n);
    for(register int i = 1;i <= n;++i)
        f[i] = (long long)f[i] * k % mod;
    exp(f,n);
    for(register int i = 1;i <= n;++i)
        printf("%d%c",f[i]," \n"[i == n]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment