板子#

1
#include<bits/stdc++.h>
2
#define ll long long
3
#define ld double
4
#define N 3000500
5
#define mod 998244353
6
const ld PI=acos(-1.0);
7
using std::string;
8
string s1,s2;
9
int read(){int p=0,flg=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') flg=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return p*flg;}
10
void write(int x){if (!x)return;write(x/10);putchar(x%10+'0');}
11
namespace Poly {
12
    int p[N],q[N],r[N],w[N],invnum[N],invfac[N],fac[N];
13
    int add(int x,int y){return x+y>mod?x+y-mod:x+y;}
14
    int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
15
    int ext(int n){return n==1?1:(1<<(std::__lg(n-1)+1));}
16
    int qpow(int a,int b){int res=1;for (;b;b>>=1,a=1ll*a*a%mod)if (b&1)res=1ll*res*a%mod;return res;}
17
    void get_r(int n){for (int i=0;i<n;i++)r[i]=(r[i>>1]>>1)|(i&1?n>>1:0);}
18
    void print(int *a,int n){for (int i=0;i<n;i++)printf("%d%c",a[i]," \n"[i==n-1]);}
19
    void init_poly(){
20
        for(int k=2,m=1;k<=N;k<<=1,m<<=1){
21
            w[m]=1;
22
            for(int i=m+1,x=qpow(3,(mod-1)/k);i<k;i++) w[i]=1ll*w[i-1]*x%mod;
23
        }invnum[1]=1;
24
        for (int i=2;i<N;i++)invnum[i]=1ll*(mod-mod/i)*invnum[mod%i]%mod;
25
        invfac[0]=1;
26
        for (int i=1;i<N;i++)invfac[i]=1ll*invfac[i-1]*invnum[i]%mod;
27
        fac[0]=1;
28
        for (int i=1;i<N;i++)fac[i]=1ll*fac[i-1]*i%mod;
29
    }
30
    void NTT(int *a,int n,int op){
31
        for (int i=0;i<n;i++)if (i<r[i])std::swap(a[i],a[r[i]]);
32
        for (int k=2,m=1;k<=n;m<<=1,k<<=1){
33
            for (int i=0;i<n;i+=k)
34
                for (int j=i,*x=w+m;j<i+m;x++,j++){
35
                    int v=1ll*a[j+m]*(*x)%mod;
36
                    a[j+m]=dec(a[j],v);a[j]=add(a[j],v);
37
                }
38
        }
39
        if (op==-1){
40
            std::reverse(a+1,a+n);
41
            for (int i=0,v=qpow(n,mod-2);i<n;i++)a[i]=1ll*a[i]*v%mod;
42
        }
43
    }
44
    void mul(int *a,int *b,int n,int m){
45
        if (!n||!m)return;
46
        int len=ext(n+m-1);
47
        for (int i=0;i<len;i++)p[i]=i<n?a[i]:0,q[i]=i<m?b[i]:0;
48
        get_r(len);
49
        NTT(p,len,1);NTT(q,len,1);
50
        for (int i=0;i<len;i++)a[i]=1ll*p[i]*q[i]%mod;
51
        NTT(a,len,-1);
52
    }
53
    void mul_2(int *a,int *b,int *c,int n,int m){
54
        if (!n||!m)return;
55
        int len=ext(n+m-1);
56
        for (int i=0;i<len;i++)p[i]=i<n?a[i]:0,q[i]=i<m?b[i]:0;
57
        get_r(len);
58
        NTT(p,len,1);NTT(q,len,1);
59
        for (int i=0;i<len;i++)c[i]=1ll*p[i]*q[i]%mod;
60
        NTT(c,len,-1);
61
    }
62
    void _inv(int *a,int *b,int n){
63
        static int c[N],d[N];
64
        n=ext(n);memset(b,0,4*n);b[0]=qpow(a[0],mod-2);
65
        for (int k=2;k<=n;k<<=1){
66
            for (int i=0;i<k<<1;i++)c[i]=i<k?a[i]:0,d[i]=i<k>>1?b[i]:0;
67
            get_r(k);NTT(d,k,1);
68
            for (int i=0;i<k;i++)d[i]=1ll*d[i]*d[i]%mod;
69
            NTT(d,k,-1);get_r(k<<1);NTT(c,k<<1,1);NTT(d,k<<1,1);
70
            for (int i=0;i<k<<1;i++)c[i]=1ll*c[i]*d[i]%mod;
71
            NTT(c,k<<1,-1);
72
            for (int i=0;i<k;i++)b[i]=(2ll*b[i]-c[i]+mod)%mod;
73
        }
74
    }
75
    void _diff(int *a,int *b,int n){//a-n个数
76
        for (int i=1;i<n;i++)b[i-1]=1ll*i*a[i]%mod;b[n-1]=0;
77
    }
78
    void _integ(int *a,int *b,int n){//b-n个数
79
        for (int i=1;i<n;i++)b[i]=1ll*invnum[i]*a[i-1]%mod;b[0]=0;
80
    }
81
    void _ln(int *a,int *b,int n){
82
        static int c[N],d[N];
83
        assert(a[0]==1);
84
        n=ext(n);
85
        _inv(a,c,n),_diff(a,d,n),mul(c,d,n,n);_integ(c,b,n);
86
    }
87
    void _exp(int *a,int *b,int n){
88
        static int c[N];
89
        assert(a[0]==0);
90
        n=ext(n);memset(b,0,4*n);memset(c,0,4*n);b[0]=1;
91
        for (int k=2;k<=n;k<<=1){
92
            _ln(b,c,k);
93
            for (int i=0;i<k;i++)c[i]=dec(a[i],c[i]);
94
            c[0]++;mul(b,c,k,k);
95

96
        }
97
    }
98
    void _sqrt(int *a,int *b,int n){
99
        static int c[N],d[N];
100
        static const int inv2=(mod+1)>>1;
101
        assert(a[0]==1);
102
        n=ext(n);memset(b,0,4*n);b[0]=1;
103
        for (int k=2;k<=n;k<<=1){
104
            memcpy(c,a,4*k);_inv(b,d,k),mul(c,d,k,k);
105
            for (int i=0;i<k;i++)b[i]=1ll*(b[i]+c[i])*inv2%mod;
106
        }
107
    }
108
    void _pow(int *a,int *b,int n,string k){
109
        static int c[N],d[N];
110
        int u=0,k1=0,k2=0;
111
        memset(b,0,4*n);
112
        for (int i=0;i<k.size();i++)k1=(10ll*k1+k[i]-'0')%mod,k2=(10ll*k2+k[i]-'0')%(mod-1);
113
        for (u=0;u<n&&!a[u];u++);
114
        if ((u&&k.size()>=5)||1ll*u*k1>=n)return;
115
        for (int i=u,x=qpow(a[u],mod-2);i<n;i++)c[i-u]=1ll*a[i]*x%mod;
116
        _ln(c,d,n-u);
117
        for (int i=0;i<n-u;i++)d[i]=1ll*d[i]*k1%mod;
118
        _exp(d,c,n-u);
119
        for (int i=u*k1,x=qpow(a[u],k2);i<n;i++)b[i]=1ll*c[i-u*k1]*x%mod;
120
    }
121
    void _pow_p(int *a,int *b,int n,string k){
122
        static int c[N],d[N];
123
        int u=0,k1=0,k2=0;
124
        for (int i=0;i<k.size();i++)k1=(10ll*k1+k[i]-'0')%mod;
125
        _ln(a,d,n);
126
        for (int i=0;i<n;i++)d[i]=1ll*d[i]*k1%mod;
127
        _exp(d,b,n);
128
    }
129
    void _div(int *a,int *b,int *q,int *r,int n,int m){
130
        static int c[N],d[N],e[N];
131
        int len=n-m+1;
132
        for (int i=0;i<len;i++)c[i]=a[n-1-i];
133
        for (int i=0;i<len;i++)d[i]=i<m?b[m-1-i]:0;
134
        _inv(d,e,len);mul(c,e,len,len),std::reverse(c,c+len);
135
        memcpy(q,c,4*len),mul(c,b,len,m);
136
        for (int i=0;i<m;i++)r[i]=dec(a[i],c[i]);
137
    }
138
    void cdq(int l,int r,int *f,int *g){
139
        static int c[N];
140
        if (l==r)return ;
141
        int mid=(l+r)>>1;
142
        cdq(l,mid,f,g);mul_2(f+l,g+1,c,mid-l+1,r-l);
143
        for (int i=mid+1;i<=r;i++)f[i]=add(f[i],c[i-l-1]);
144
        cdq(mid+1,r,f,g);
145
    }
146
}
147
using namespace Poly;
148
int n,m;int a[N],b[N],Q[N],R[N];
149
string k;
150
void solve(){
151
    scanf("%d",&n);
152
    for (int i=1;i<n;i++)scanf("%d",a+i);b[0]=1;
153
    cdq(0,n-1,b,a);
154
    print(b,n);
155
}
156
int main(){
157
    int t=1;
158
    init_poly();
159
    // scanf("%d",&t);
160
    while (t--){
161
        solve();
162
    }
163
    return 0;
164
}

$Euler$ 变换#

$F(x)=\sum_{i}f_ix^i$
第一个定义式
$\varepsilon(F(x))=\prod_{i}\frac{1}{(1-x^i)^{f_i}}$
$Euler$ 变换的组合意义：无标号的 $n$ 个球，分成若干非空组，大小为 $i$ 的组内部具有 $f_i$ 中方案数，为最后的总方案数（如果两个组大小和内部方案相同，则他们不可区分）
注： $\frac{1}{1-x^i}$ 在枚举有几个大小为 $i$ 的组， $f_i$ 是大小为 $i$ 的内部的方案数
第二种定义式

\begin{align} \varepsilon(F(x))&=\prod_{i}\frac{1}{(1-x^i)^{f_i}}\\ &=\exp(\ln(\prod_{i}\frac{1}{(1-x^i)^{f_i}}))\\ &=\exp(\sum_{i}-f_i\ln(\frac{1}{1-x^i})\\ &=\exp(\sum_{i}-f_i\sum_j\frac{-x^{ij}}{j})\\ &=\exp(\sum_{j}\sum_if_i\frac{x^{ij}}{j})\\ &=\exp(\sum_j\frac{F(x^j)}{j})\\ \end{align}

分治 $FFT$
$1.f_{n}=t(n)\sum_{i=1}^{n}f_{i}g_{n-i}$
考虑分治区间 $[l,r]$
已经计算完 $[l,mid]$
此时 $[l,mid]$ 的 $f$ 值是已知的
又因为，在递归 $[mid+1,r]$ 时，需保证 $[1,mid]$ 的贡献已经计算
也就是说我们需要处理 $[l,mid]$ 的 $f$ 对 $[mid+1,r]$ 的 $f$ 的贡献
$f$ 的下标是 $[l,mid]$ ，由于要覆盖 $[mid+1,r]$ ，所以 $g$ 的下标是 $[1,r-l]$
$f_{l,\dots,mid}\times g_{1,\dots,r-l}\to f_{mid+1,\dots,r}$
对于 $t(n)$ ，我们保证转移的时候 $f$ 是正确求出的
所以在递归到 $[n,n]$ 时，我们在将 $t(n)$ 乘上
$2.f_n=\frac{1}{n-1}\sum_{i=1}^{n}f_ig_{n-i},g_{n}=\sum_{d\mid n}^{n}df_d,f_1=1$
这种相互递归的式子
我们仍然考虑分治区间 $[l,r]$
已经计算完 $[l,mid]$ 的所有值，现在的问题是 $g$ 在 $[mid+1,r]$ 上的值还没有计算完
$r-l\le mid\to r\le 3l$
条件很难满足
考虑我们能不能分别计算
现在应该是 $[0,mid]$ 已知
我们若按照之前的算法计算
$f_{l,\dots,mid}\times g_{1,\dots,mid}\to f_{mid+1,\dots,r}$
此时少了 $g$ 在 $[mid+1,r-l]$ 上的贡献
我们考虑分治过程中 $l,r$ 的关系
只考虑分治到右边，左边同第一个
此时区间为 $[mid+1,r]$ ，则在之后的任何区间内，都有
$r\le 2l$ 也就是 $r-l\le l$
所以，只要 $l\neq 1$ ，那么 $r-l\le l$ ，
对 $l=1$ 时：
先计算 $f_{1,\dots,mid}\times g_{1,\dots,mid}\to f_{mid+1,\dots,r}$
此时，只有 $f_{mid}$ 是正确的，
继续递归到下个区间
现在 $l\neq1$ ，那么我们会有 $f_{1,\dots,r-l},g_{1,\dots,r-l}$ 都是已知的
先计算完 $[l,mid]$ 区间，
我们已经计算完 $f_{1,l-1}\times g_{1,l-1}(1)$
已知
$f_{i}=t(i)\sum_{j=1}^{i-1}f_{j}g_{i-j}$
所以我们需要计算

\begin{cases} f_{l,mid}\times g_{1,r-l}\to f_{mid+1,r}(2)\\ f_{1,r-l}\times g_{l,mid}\to f_{mid+1,r}(3)\\ \end{cases}

我们考虑为什么这是对的
$[mid+1,r]$ 的贡献来自 $[1,l-1],[l,mid]$
$(1)$ 计算 $[1,l-1]$ 的贡献
$(2)(3)$ 计算 $[1,l-1]$ 与 $[l,mid]$ 的交叉结果
由于 $r-l\le l$ 所以， $[l,mid]$ 的内部交叉无贡献
发现我们每次这样计算的时候都是计算好了 $[l,mid]$ 对后面区间的贡献
所以这样是正确的
即
$l=1$ 时
$f_{1,,mid}\times g_{1,,mid}\to f_{mid+1,,r}$
$l\neq1$ 时

\begin{cases} f_{l,mid}\times g_{1,r-l}\to f_{mid+1,r}(2)\\ f_{1,r-l}\times g_{l,mid}\to f_{mid+1,r}(3)\\ \end{cases}

板子#

EulerEulerEuler变换#

$Euler$ 变换#