BZOJ3684: 大朋友和多叉树

Description#

我们的大朋友很喜欢计算机科学，而且尤其喜欢多叉树。对于一棵带有正整数点权的有根多叉树，如果它满足这样的性质，我们的大朋友就会将其称作神犇的：点权为1的结点是叶子结点；对于任一点权大于1的结点u，u的孩子数目deg[u]属于集合D，且u的点权等于这些孩子结点的点权之和。给出一个整数s，你能求出根节点权值为s的神犇多叉树的个数吗？请参照样例以更好的理解什么样的两棵多叉树会被视为不同的。我们只需要知道答案关于950009857（453*2^21+1，一个质数）取模后的值。

Input#

第一行有2个整数s,m。第二行有m个互异的整数，d[1],d[2],…,d[m]，为集合D中的元素。

Output#

输出一行仅一个整数，表示答案模950009857的值。

Sample Input#

Sample Output#

1
10

HINT#

数据规模： $1 \leq m < s \leq 10^5$ , $2 \leq d[i] \leq s$ ，有3组小数据和3组大数据。

题解#

求出树的生成函数 $T(x) = \sum_{i\ge 0} t_ix^i$ $T(x) = x + \sum_{k \in S}T(x)^k$

移一下项 $T(x) - \sum_{k \in S}T(x)^k = x$

设 $G(y) = y - \sum_{k \in S}{y^k}$

$x = G(T(x))$

$T(x)$ 为 $G(x)$ 的复合逆

上拉格朗日反演

$[x^n]T(x) = \frac{1}{n}[x^{n-1}] ( \frac {x}{G(x)} )^n$

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int MOD = 950009857;
6
const int MAXN = 2e6 + 5;
7
inline int read()
8
{
9
    int x=0,f=1;char ch=getchar();
10
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
12
    return x*f;
13
}
14
long long pow_mod(long long a, int b)
15
{
16
    long long ans = 1;
17
    while (b)
18
    {
19
        if (b & 1) ans = ans * a % MOD;
20
        b >>= 1;
21
        a = a * a % MOD;
22
    }
23
    return ans;
24
}
25
int rev[MAXN];
26
int Inv;
27
void FFt(int *a, int N, int op)
28
{
29
    int w, wn, t;
30
    for (int i = 1; i < N; i++)
31
        if (i < rev[i])
32
            swap(a[i], a[rev[i]]);
33
    for (int k = 2; k <= N; k <<= 1)
34
    {
35
        wn = pow_mod(7, op == 1 ? (MOD - 1) / k : MOD - 1 - (MOD - 1) / k);
36
        for (int j = 0; j < N; j += k)
37
        {
38
            w = 1;
39
            for (int i = 0; i < (k >> 1); i++, w = 1ll * w * wn % MOD)
40
            {
41
                t = 1ll * a[i + j + (k >> 1)] * w % MOD;
42
                a[i + j + (k >> 1)] = (a[i + j] - t + MOD) % MOD;
43
                a[i + j] = (a[i + j] + t) % MOD;
44
            }
45
        }
46
    }
47
    if (op == -1)
48
        for (int i = 0; i < N; i++)
49
            a[i] = 1ll * a[i] * Inv % MOD;
50
}
51
int tmp[MAXN];
52
void Get_Inv(int dep, int *a, int *b)
53
{
54
    if (dep == 1) return b[0] = pow_mod(a[0], MOD - 2), void();
55
    Get_Inv((dep + 1) >> 1, a, b);
56
    int N = 1;
57
    while (N < (dep << 1))
58
        N <<= 1;
59
    Inv = pow_mod(N, MOD - 2);
60
    for (int i = 1; i < N; i++)
61
        if (i & 1)
62
            rev[i] = (rev[i >> 1] >> 1) | (N >> 1);
63
        else
64
            rev[i] = (rev[i >> 1] >> 1);
65
    //copy(a, a + dep, tmp);
66
    for (int i = 0; i < dep; i++)
67
        tmp[i] = a[i];
68
    for (int i = dep; i < N; i++)
69
        tmp[i] = 0;
70
    //fill(tmp + dep, tmp + N, 0);
71
    FFt(tmp, N, 1);
72
    FFt(b, N, 1);
73
    for (int i = 0; i < N; i++)
74
        b[i] = 1ll * b[i] * ((2 - 1ll * b[i] * tmp[i] % MOD + MOD) % MOD) % MOD;
75
    FFt(b, N, -1);
76
    for (int i = dep; i < N; i++)
77
        b[i] = 0;
78
    //fill(b + dep, b + N, 0);
79
}
80
int G[MAXN], Ans[MAXN], C[MAXN];
81
int main()
82
{
83
    int n = read(), m = read();
84
    C[0] = 1;
85
    for (int i = 1; i <= m; i++)
86
        C[read() - 1] = MOD - 1;
87
    Get_Inv(n, C, G);
88
    Ans[0] = 1;
89
    int b = n;
90
    int N = 1;
91
    while (N < 2 * n)
92
        N <<= 1;
93
    Inv = pow_mod(N, MOD - 2);
94
    for (int i = 1; i < N; i++)
95
        if (i & 1)
96
            rev[i] = (rev[i >> 1] >> 1) | (N >> 1);
97
        else
98
            rev[i] = (rev[i >> 1] >> 1);
99
    while (b)
100
    {
101
        if (b & 1)
102
        {
103
            FFt(Ans, N, 1);
104
            FFt(G, N, 1);
105
            for (int i = 0; i < N; i++) Ans[i] = 1ll * Ans[i] * G[i] % MOD;
106
            FFt(Ans, N, -1);
107
            FFt(G, N, -1);
108
            for (int i = n; i < N; i++)
109
                Ans[i] = 0;
110
        }
111
        b >>= 1;
112
        FFt(G, N, 1);
113
        for (int i = 0; i < N; i++) G[i] = 1ll * G[i] * G[i] % MOD;
114
        FFt(G, N, -1);
115
        for (int i = n; i < N; i++)
116
            G[i] = 0;
117
        // fill(G + n, G + N, 0);
118
    }
119
    printf ("%d\n", 1ll * Ans[n - 1] * pow_mod(n, MOD - 2) % MOD);
120
}