JZOJ 5031 B

发表于 | 分类于 |

乐色出题人，这种题开 3s，标算还是 \(O(n \log n \log k)\) 做法？
如果你是需要多项式快速幂，在能 ln / exp 的情况下放个这个复杂度可还行，但是这个快速幂可以直接算啊好不好（

首先显然有 \(g = f * \textbf 1^k\)。

然后显然做狄利克雷卷积快速幂即可。

然后显然有 \(\textbf 1^k(p^c) = \binom{c+k-1}{c-1}\)。
线性筛然后做一次卷积即可。

然而我一开始以为 \(g = f^k\)。
然后就被叫去当苦力了。
所以我整了个 DGF ln / exp 的板子（
然后发现问题之后懒得改掉了（
就这样做了（
反正也是 \(O(n \log n)\).jpg（

代码： 

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
73
74
75
76
77
78
79
#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 = 1e5;
const int mod = 1e9 + 7;
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 T,n,k;
int f[N + 5],g[N + 5],h[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()
{
    freopen("b.in","r",stdin),freopen("b.out","w",stdout);
    scanf("%d",&T);
    for(;T;--T)
    {
        scanf("%d%d",&n,&k);
        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;
            }
        }
        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",h + i),f[i] = 1;
        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 = n;i;--i)
            for(register int j = 2;i * j <= n;++j)
                h[i * j] = (h[i * j] + (long long)h[i] * f[j]) % mod;
        for(register int i = 1;i <= n;++i)
            printf("%d%c",h[i]," \n"[i == n]);
    }
}