Chaos Slover 补档计划 - 捱-捱-䫮的高级应用

2015.12.09 10:35 Wed| 37 visits oi_2016| ChaosSlover补档计划| Text

BZOJ3771 Triple

这个题,n 的范围是什么呢?是什么呢……ai 互不相同,是什么呢?

把给出的序列的生成函数 $F(x) = x^{a_1}+x^{a_2}+...+x^{a_n}$ 自乘 T 次,得到的式子中的第 i 项系数表示“每一种斧头都有无穷多,有顺序地拿走 T 个斧头,使得斧头价值之和为 i 的方案数”。

那么可以发现,我们能够直接用 FFT 求出的东西和我们想要求出的东西只有两个差别:元素个数和顺序。顺序可以通过除以阶乘消去,元素个数可以通过容斥减去,这个题就结束了。

 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
#include <bits/stdc++.h>
using namespace std;
#define N 131072

int n;
long long f[N], g[N], h[N], f2[N], f3[N], fg[N];
complex<double> a[N], b[N], c[N], d[N];
const double pi = 3.14159265358979323;

void fft(complex<double> x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        complex<double> wn(cos(type * 2 * pi / s), sin(type * 2 * pi / s));
        for (int i = 0; i < n; i += s)
        {
            complex<double> w(1, 0), t;
            for (int j = 0; j < s >> 1; w *= wn, ++j)
                t = w * x[i + j + (s >> 1)],
                x[i + j + (s >> 1)] = x[i + j] - t, x[i + j] += t;
        }
    }
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n;
    for (int x, i = 1; i <= n; ++i)
        f[x = read()] = 1, g[x * 2] = 1, h[x * 3] = 1;
    int s = 131072;
    for (int i = 0; i < s; ++i)
        a[i] = f[i], d[i] = g[i];
    fft(a, s, 1), fft(d, s, 1);
    for (int i = 0; i < s; ++i)
        b[i] = a[i] * a[i], c[i] = b[i] * a[i], d[i] *= a[i];
    fft(b, s, -1), fft(c, s, -1), fft(d, s, -1);
    for (int i = 0; i < s; ++i)
        f2[i] = b[i].real() / s + 0.1, f3[i] = c[i].real() / s + 0.1,
        fg[i] = d[i].real() / s + 0.1;
    for (int i = 0; i < s; ++i)
    {
        long long t = (f3[i] - 3 * fg[i] + 2 * h[i]) / 6 +
                      (f2[i] - g[i]) / 2 + f[i];
        if (t) printf("%d %lld\n", i, t);
    }
    return 0;
}

Nescafe41 异化多肽(polypeptide.pas/c/cpp)

题目描述

多肽是 α-氨基酸以肽键连接在一起而形成的化合物,它也是蛋白质水解的中间产物。由两个氨基酸分子脱水缩合而成的化合物叫做二肽,同理类推还有三肽、四肽、五肽等。通常由三个或三个以上氨基酸分子脱水缩合而成的化合物都可以成为叫多肽。

为了计算病毒结构与蛋白质性质,现取出M种氨基酸混合,已知其相对分子质量分别为 C1,C2,C3……,经过精密的脱水缩合后形成了大量各种各样的肽链。需要预测有多少种多肽链水解后相对分子质量和为 N。(A-B-C 与 C-B-A 两条肽链视为不同)

输入格式

第一行两个整数 N, M 第二行 M 个整数分别表示氨基酸的相对分子质量。

输出格式

一个整数表示方案数除以 1005060097 的余数。

样例输入

4 2
1 2

样例输出

5

数据范围和注释

对于30%的数据,N,M,C≤5000。

对于100%的数据,N,M,C≤100000。

题目解答

对于 30% 的数据:

设 F(n) 表示相对分子质量和为 n 的肽链个数,C(n)为可选氨基酸中相对分子质量为 n 的氨基酸有多少种,可有递推式 F(n)=∑F(n-k)*C(k),故 O(n^2) 即可求解(a^b 表示 a 的 b 次幂)。

对于 100% 的数据:

此问题等价于将正整数 N 有序拆分为若干集合 C 中数之和的方案数,依据 M 个数字 Ci 构造多项式 C=∑ckxk,ck 为集合 C 中数字 k 的个数;构造形式幂级数 ∑akxk,ak 为将正整数 k 按集合 C 拆分的方案数。

依据乘法原理有 G=(1+C+C2+C3+…)=1/(1-C) ,或根据递推式 G=CG+1 也可解得 G=1/(1-C)。由于只需求 G 中的第 N 项,故将所有多项式在 (mod xN+1) 意义下求解即可,故原题的答案序列为多项式 1-C 的逆元,用快速傅里叶变换即可 O(N*logN) 求解,可通过全部数据。

 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 <bits/stdc++.h>
using namespace std;

#define N 262150
#define P 1005060097
#define G 5

int power(int a, int b)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % P;
        a = 1ll * a * a % P, b >>= 1;
    }
    return re;
}

void ntt(int x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        int wn = power(G, (P - 1) / s);
        for (int i = 0; i < n; i += s)
            for (int w = 1, t, j = 0; j < s >> 1; w = 1ll * w * wn % P, ++j)
                t = 1ll * w * x[i + j + (s >> 1)] % P,
                x[i + j + (s >> 1)] = (x[i + j] - t + P) % P,
                x[i + j] = (x[i + j] + t) % P;
    }
    if (type == -1)
    {
        reverse(x + 1, x + n);
        int inv = power(n, P - 2);
        for (int i = 0; i < n; ++i)
            x[i] = 1ll * x[i] * inv % P;
    }
}

void getinv(int a[], int b[], int n)
{
    static int c[N];
    if (n == 1) { b[0] = power(a[0], P - 2); return; }
    getinv(a, b, n >> 1);
    memcpy(c, a, n * sizeof(int));
    ntt(c, n << 1, 1); ntt(b, n << 1, 1);
    for (int i = 0; i < n << 1; ++i)
        c[i] = 1ll * b[i] * (2 - 1ll * b[i] * c[i] % P + P) % P;
    ntt(c, n << 1, -1);
    memcpy(b, c, n * sizeof(int));
    memset(b + n, 0, n * sizeof(int));
}

int n, m, f[N], g[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    freopen("polypeptide.in", "r", stdin);
    freopen("polypeptide.out", "w", stdout);
    cin >> n >> m;
    f[0] = 1;
    for (int x, i = 1; i <= m; ++i)
        x = read(), f[x] = (f[x] + P - 1) % P;
    getinv(f, g, 131072);
    cout << g[n] << endl;
    return 0;
}

求奇怪的素数的原根(简易版)

虽然慢,但是很好写。听说原根的个数约为 $\varphi(\varphi(P))$,所以我们期望原根很小。当枚举不是原根的数的时候,循环内执行次数也不会特别多(为 P - 1 的约数)。因此这个暴力算法大概可以是很实用的吧。

1005060097 这个素数的最小原根是 5,还有一个原根是 7。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int p;

int main()
{
    cin >> p;
    for (int i = 2; i < p; ++i)
    {
        printf("now checking for %d\n", i);
        int t = 1;
        for (int j = 1; j < p; ++j)
        {
            if (j == p - 1)
                { printf("%d is an primitive root\n", i); break; }
            if ((t = 1ll * t * i % p) == 1)
                { printf("%d is not an primitive root at %d\n", i, j); break; }
        }
    }
}

BZOJ3625&CF250E 小朋友和二叉树

设集合 C 的生成函数为 C(x),答案函数为 F(x),有如下递归式:

用公式解二次方程:

由于 C(x) 无常数项,即分母无常数项,所以分子也不能有常数项,否则就不存在逆了。所以在分子上只能取减号,用开方开出来的 1 消去常数项。

上下同乘一个共轭根式(不乘共轭根式的话分母常数项还是 0,然而乘一下之后就可以约分了,常数项就不是 0 了),得到

然后跑一个多项式开根……时间复杂度还是丧心病狂的 O(N*logN)。

在多项式开根算法中,我们需要先算出来第零项取值为 $\sqrt{A[0]}(\bmod x)$,然后使用倍增就能够推出来了。

  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
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>
using namespace std;

#define N 262150
#define P 998244353
#define G 3

int power(int a, int b)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % P;
        a = 1ll * a * a % P, b >>= 1;
    }
    return re;
}

void ntt(int x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        int wn = power(G, (P - 1) / s);
        for (int i = 0; i < n; i += s)
            for (int w = 1, t, j = 0; j < s >> 1; w = 1ll * w * wn % P, ++j)
                t = 1ll * w * x[i + j + (s >> 1)] % P,
                x[i + j + (s >> 1)] = (x[i + j] - t + P) % P,
                x[i + j] = (x[i + j] + t) % P;
    }
    if (type == -1)
    {
        reverse(x + 1, x + n);
        int inv = power(n, P - 2);
        for (int i = 0; i < n; ++i)
            x[i] = 1ll * x[i] * inv % P;
    }
}

void getinv(int a[], int b[], int n)
{
    static int c[N];
    if (n == 1) { b[0] = power(a[0], P - 2); return; }
    getinv(a, b, n >> 1);
    memcpy(c, a, n * sizeof(int));
    memset(c + n, 0, n * sizeof(int));
    ntt(c, n << 1, 1), ntt(b, n << 1, 1);
    for (int i = 0; i < n << 1; ++i)
        c[i] = 1ll * b[i] * (2 - 1ll * b[i] * c[i] % P + P) % P;
    ntt(c, n << 1, -1);
    memcpy(b, c, n * sizeof(int));
    memset(b + n, 0, n * sizeof(int));
}

void getsqrt(int a[], int b[], int n)
{
    static int c[N], _b[N];
    if (n == 1) { b[0] = 1; return; }
    getsqrt(a, b, n >> 1);
    memset(_b, 0, 2 * n * sizeof(int));
    getinv(b, _b, n);
    memcpy(c, a, n * sizeof(int));
    memset(c + n, 0, n * sizeof(int));
    ntt(c, n << 1, 1), ntt(b, n << 1, 1), ntt(_b, n << 1, 1);
    for (int i = 0; i < n << 1; ++i)
        c[i] = 1ll * (P + 1) / 2 * (b[i] + 1ll * _b[i] * c[i] % P) % P;
    ntt(c, n << 1, -1);
    memcpy(b, c, n * sizeof(int));
    memset(b + n, 0, n * sizeof(int));
}

int n, m, f[N], g[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> m;
    f[0] = 1;
    for (int i = 1; i <= n; ++i)
        f[read()] = P - 4;
    int t = 1; while (t <= m) t <<= 1;
    getsqrt(f, g, t);
    ++g[0];
    memset(f, 0, sizeof f);
    getinv(g, f, t);
    for (int i = 1; i <= m; ++i)
        printf("%d\n", f[i] * 2 % P);
    return 0;
}

BZOJ3456 城市规划

求多项式的 ln,有如下公式:

对于多项式,求导和积分的操作都可以在 O(N) 的时间内完成(就是扫一遍乘以乘除一除什么的)。

然后这个题需要用到指数的生成函数推公式。

设 G(x) 为简单无向图的指数生成函数,F(x) 为简单无向连通图的指数生成函数,有:

另外我们很容易求得 G(x):

这样就结束了。注意不能忘记在生成函数下面有一个阶乘,那也是系数……

  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
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
using namespace std;

#define N 262150
#define P 1004535809
#define G 3

int power(int a, long long b)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % P;
        a = 1ll * a * a % P, b >>= 1;
    }
    return re;
}

void ntt(int x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        int wn = power(G, (P - 1) / s);
        for (int i = 0; i < n; i += s)
            for (int w = 1, t, j = 0; j < s >> 1; w = 1ll * w * wn % P, ++j)
                t = 1ll * w * x[i + j + (s >> 1)] % P,
                x[i + j + (s >> 1)] = (x[i + j] - t + P) % P,
                x[i + j] = (x[i + j] + t) % P;
    }
    if (type == -1)
    {
        reverse(x + 1, x + n);
        int inv = power(n, P - 2);
        for (int i = 0; i < n; ++i)
            x[i] = 1ll * x[i] * inv % P;
    }
}

void getinv(int a[], int b[], int n)
{
    static int c[N];
    if (n == 1) { b[0] = power(a[0], P - 2); return; }
    getinv(a, b, n >> 1);
    memcpy(c, a, n * sizeof(int));
    memset(c + n, 0, n * sizeof(int));
    ntt(c, n << 1, 1), ntt(b, n << 1, 1);
    for (int i = 0; i < n << 1; ++i)
        c[i] = 1ll * b[i] * (2 - 1ll * b[i] * c[i] % P + P) % P;
    ntt(c, n << 1, -1);
    memcpy(b, c, n * sizeof(int));
    memset(b + n, 0, n * sizeof(int));
}

void getsqrt(int a[], int b[], int n)
{
    static int c[N], _b[N];
    if (n == 1) { b[0] = 1; return; }
    getsqrt(a, b, n >> 1);
    memset(_b, 0, 2 * n * sizeof(int));
    getinv(b, _b, n);
    memcpy(c, a, n * sizeof(int));
    memset(c + n, 0, n * sizeof(int));
    ntt(c, n << 1, 1), ntt(b, n << 1, 1), ntt(_b, n << 1, 1);
    for (int i = 0; i < n << 1; ++i)
        c[i] = 1ll * (P + 1) / 2 * (b[i] + 1ll * _b[i] * c[i] % P) % P;
    ntt(c, n << 1, -1);
    memcpy(b, c, n * sizeof(int));
    memset(b + n, 0, n * sizeof(int));
}

void getln(int a[], int b[], int n)
{
    static int c[N], d[N];
    memset(c, 0, 2 * n * sizeof(int));
    getinv(a, c, n);
    memset(d, 0, 2 * n * sizeof(int));
    for (int i = 1; i < n; ++i)
        d[i - 1] = 1ll * i * a[i] % P;
    ntt(c, n << 1, 1), ntt(d, n << 1, 1);
    for (int i = 0; i < n << 1; ++i)
        c[i] = 1ll * c[i] * d[i] % P;
    ntt(c, n << 1, -1);
    for (int i = 1; i < n; ++i)
        b[i] = 1ll * power(i, P - 2) * c[i - 1] % P;
}

int n, m, f[N], g[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n;
    int t = 1;
    f[0] = 1; f[1] = 1;
    for (int i = 2; i <= n; ++i)
        t = 1ll * t * i % P,
        f[i] = 1ll * power(2, 1ll * i * (i - 1) / 2) * power(t, P - 2) % P;
    int s = 1;
    while (s <= n) s <<= 1;
    getln(f, g, s);
    cout << 1ll * g[n] * t % P << endl;
    return 0;
}

BZOJ3684 大朋友和多叉树

这道题的具体题解去看大爷写的吧。

到此为止,关于多项式运算的各种操作的模板也基本成型了。感觉都差不多,然而重点是背下来所有的公式(这才是最困难的啊)……

关于拉格朗日反演什么的, 网上的资料很少(基本没有)。也就是一个公式而已嘛,往里代数就好了。反正现在的我看到这种题大概也推不出来方程 233。

  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
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
using namespace std;

#define N 262150
#define P 950009857
#define G 7

int power(int a, long long b)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % P;
        a = 1ll * a * a % P, b >>= 1;
    }
    return re;
}

void ntt(int x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        int wn = power(G, (P - 1) / s);
        for (int i = 0; i < n; i += s)
            for (int w = 1, t, j = 0; j < s >> 1; w = 1ll * w * wn % P, ++j)
                t = 1ll * w * x[i + j + (s >> 1)] % P,
                x[i + j + (s >> 1)] = (x[i + j] - t + P) % P,
                x[i + j] = (x[i + j] + t) % P;
    }
    if (type == -1)
    {
        reverse(x + 1, x + n);
        int inv = power(n, P - 2);
        for (int i = 0; i < n; ++i)
            x[i] = 1ll * x[i] * inv % P;
    }
}

void getinv(int a[], int b[], int n)
{
    static int c[N];
    if (n == 1) { b[0] = power(a[0], P - 2); return; }
    getinv(a, b, n >> 1);
    memcpy(c, a, n * sizeof(int));
    memset(c + n, 0, n * sizeof(int));
    ntt(b, n << 1, 1), ntt(c, n << 1, 1);
    for (int i = 0; i < n << 1; ++i)
        b[i] = 1ll * b[i] * (2 - 1ll * b[i] * c[i] % P + P) % P;
    ntt(b, n << 1, -1);
    memset(b + n, 0, n * sizeof(int));
}

void getsqrt(int a[], int b[], int n)
{
    static int c[N], d[N];
    if (n == 1) { b[0] = 1; return; }
    getsqrt(a, b, n >> 1);
    memset(d, 0, 2 * n * sizeof(int));
    getinv(b, d, n);
    memcpy(c, a, n * sizeof(int));
    memset(c + n, 0, n * sizeof(int));
    ntt(b, n << 1, 1), ntt(c, n << 1, 1), ntt(d, n << 1, 1);
    for (int i = 0; i < n << 1; ++i)
        b[i] = 1ll * (P + 1) / 2 * (b[i] + 1ll * d[i] * c[i] % P) % P;
    ntt(b, n << 1, -1);
    memset(b + n, 0, n * sizeof(int));
}

void getln(int a[], int b[], int n)
{
    static int c[N], d[N];
    memset(c, 0, 2 * n * sizeof(int));
    getinv(a, c, n);
    memset(d, 0, 2 * n * sizeof(int));
    for (int i = 1; i < n; ++i)
        d[i - 1] = 1ll * i * a[i] % P;
    ntt(c, n << 1, 1), ntt(d, n << 1, 1);
    for (int i = 0; i < n << 1; ++i)
        c[i] = 1ll * c[i] * d[i] % P;
    ntt(c, n << 1, -1);
    for (int i = 1; i < n; ++i)
        b[i] = 1ll * power(i, P - 2) * c[i - 1] % P;
}

void getexp(int a[], int b[], int n)
{
    static int c[N];
    if (n == 1) { b[0] = 1; return; }
    getexp(a, b, n >> 1);
    memset(c, 0, 2 * n * sizeof(int));
    getln(b, c, n);
    for (int i = 0; i < n; ++i)
        c[i] = ((i == 0) - c[i] + a[i] + P) % P;
    ntt(b, n << 1, 1), ntt(c, n << 1, 1);
    for (int i = 0; i < n << 1; ++i)
        b[i] = 1ll * b[i] * c[i] % P;
    ntt(b, n << 1, -1);
    memset(b + n, 0, n * sizeof(int));
}

void getpower(int a[], int b[], int k, int n)
{
    static int c[N];
    memset(c, 0, 2 * n * sizeof(int));
    getln(a, c, n);
    for (int i = 0; i < n; ++i)
        c[i] = 1ll * c[i] * k % P;
    getexp(c, b, n);
}

int s, m, f[N], g[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> s >> m;
    f[0] = 1;
    for (int x, i = 1; i <= m; ++i)
        x = read() - 1, f[x] = (f[x] - 1 + P) % P;
    int t = 1;
    while (t <= s) t <<= 1;
    getinv(f, g, t);
    memset(f, 0, sizeof f);
    getpower(g, f, s, t);
    cout << 1ll * f[s - 1] * power(s, P - 2) % P << endl;
    return 0;
}

总结

简单总结一下各种运算的适用范围吧。

多项式存在逆的充要条件是它的常数项存在逆,也就是常数项不为零。

多项式的平方根存在当且仅当多项式为0或最低项次数为偶数,多项式开根时我们要先除 x 的几次方使得它的常数项不为 0,然后还需要先求出来它的常数项的一个根。

模意义下 $\ln F(x)$ 有意义当且仅当 $[0]F(x)=1$。

利用 exp 快速求多项式的幂时需要保证多项式的常数项为 1,否则需要进行一些处理。然而在它不为 1 的时候,我选择快速幂。

多项式的 k 次方根大概就是 k 的逆元次方,需要注意的还是常数项需要为 1。我拿这种方式去交《小朋友与二叉树》,然后 BZOJ TLE,CF AC 了……

拉格朗日(学日语的后遗症:打字的时候总达成 ra 格 rang 日什么的)反演公式及一个推广:

若 F(x) 是 G(x) 的复合逆,那么满足: