前置理论

期望的线性性

$$E(a\cdot b)=E(a)\cdot E(b)$$

整数 $k$次幂和

方法 1:

$$1+a_1^1x+a_1^2x^2+a_1^3x^3+\cdots+\\ 1+a_2^1x+a_2^2x^2+a_2^3x^3+\cdots +\\ \cdots \\$$

$$\frac{1}{1-a_1x}+\frac{1}{1-a_2x}+\cdots+\frac{1}{1-a_nx}$$

方法 2：

$$ln(1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+\cdots \\ ln(1+ax)=ax-\frac{a^2x^2}{2}+\frac{a^3x^3}{3}-\frac{a^4x^4}{4}+\cdots$$

$$\sum_{i=1}^nln(1+a_ix)=ln(\Pi_{i=1}^{n}(1+a_ix))$$

$$F=ln(\Pi_{i=1}^{n}(1+a_ix))$$

$$ln(x)’=\frac{1}{x} \\ ln(x)=\int \frac{1}{x}$$

$$T(n)=T(\frac{n}{2})+O(nlogn)$$

题目分析

$$E(x+y)^t=\sum_{i=0}^tC_t^iE(x^i)E(y^{t-i})$$

\begin{aligned} F(t)& =\sum_{i=0}^tC_t^iA(i)B(t-i) \\ F(t)& =\sum_{i=0}^t\frac{t!}{i!(t-i)!}A(i)B(t-i) \\ \frac{1}{t!}F(t)& =\sum_{i=0}^t\frac{1}{i!}A(i)\cdot\frac{1}{t-i}B(t-i) \end{aligned}

更快的 NTT

• 1. 将一切可以预处理的东西预处理
• 2. 将一切可以省略的取模省略

void dft(int f)
{
for(int i=0;i<len;i++)if(i<rev[i])swap(x[i],x[rev[i]]);
for(int w=1;w<len;w<<=1)
{
ll w1=ksm(G,(MOD-1)/(w<<1));
if(f==-1)w1=inv(w1);
for(int j=0;j<len;j+=(w<<1))
{
ll wn=1;
for(int i=j;i<j+w;i++)
{
ll a=x[i],b=x[i+w];
x[i]=(a+wn*b)%MOD;
x[i+w]=(a-wn*b%MOD+MOD)%MOD;
wn=wn*w1%MOD;
}
}
}
if(f==-1)
{
ll mul=ksm(len,MOD-2);
for(int i=0;i<len;i++)x[i]=x[i]*mul%MOD;
}
}

void dft(int f)
{
for(int i=0;i<len;i++)if(i<rev[i])swap(x[i],x[rev[i]]);
for(int w=1,b=1;w<len;w<<=1,b++)
{
ll *wx=(f==1?wi[b]:wii[b]);     //wi 和 wii 为原根的幂及幂的逆
for(int j=0;j<len;j+=(w<<1))
{
for(int i=j;i<j+w;i++)
{
ll a=x[i],b=wx[i-j]*x[i+w];
x[i]=(a+b)%MOD;
x[i+w]=(a-b+MOD*MOD)%MOD;
}
}
}
if(f==-1)
{
ll mul=ksm(len,MOD-2);
for(int i=0;i<len;i++)x[i]=x[i]*mul%MOD;
}
}

代码

#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"

#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX (524288+10)
#define MOD 998244353LL
#define G 3

using namespace std;

typedef long long ll;

int len,bit,rev[MX];
int n1,n2,m,A[MX],B[MX];
ll fac[MX];
ll EA[MX],EB[MX];
ll gp[MX],gpi[MX],wi[22][MX],wii[22][MX];

{
ll x=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x;
}

void qm(ll& x){x%=MOD;if(x<0)x+=MOD;}

void init(int l)
{
len=1,bit=0,rev[0]=0;
while(len<l)len<<=1,bit++;
for(int i=1;i<len;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
}

ll ksm(ll x,ll t)
{
ll ans=1;
while(t)
{
if(t&1)ans=ans*x%MOD;
x=x*x%MOD;
t>>=1;
}
return ans;
}

ll inv(ll x){return ksm(x,MOD-2);}

struct poly
{
ll *x;
void resize(){delete x;x=new ll[len];memset(x,0,len*sizeof(ll));}
void reset(){memset(x,0,len*sizeof(ll));}
void input(int s){for(int i=0;i<s;i++)scanf("%lld",&x[i]),qm(x[i]);}
void output(int s){for(int i=0;i<s;i++)printf("%lld ",x[i]);putchar('\n');}
void dft(int f)
{
for(int i=0;i<len;i++)if(i<rev[i])swap(x[i],x[rev[i]]);
for(int w=1,b=1;w<len;w<<=1,b++)
{
ll *wx=(f==1?wi[b]:wii[b]);
for(int j=0;j<len;j+=(w<<1))
{
for(int i=j;i<j+w;i++)
{
ll a=x[i],b=wx[i-j]*x[i+w];
x[i]=(a+b)%MOD;
x[i+w]=(a-b+MOD*MOD)%MOD;
}
}
}
if(f==-1)
{
ll mul=ksm(len,MOD-2);
for(int i=0;i<len;i++)x[i]=x[i]*mul%MOD;
}
}
};

poly up[MX],dn[MX];
poly dl,ul,dr,ur,dv,f1,f2;
poly tmp;

void get_inv(poly &a,poly &b,int nx)
{
if(nx==1)b.x[0]=inv(a.x[0]);
else
{
get_inv(a,b,nx>>1);
for(int i=0;i<nx;i++)tmp.x[i]=a.x[i],tmp.x[i+nx]=0;
init(nx<<1);
tmp.dft(1);
b.dft(1);
for(int i=0;i<len;i++)
tmp.x[i]=(b.x[i]*2-tmp.x[i]*b.x[i]%MOD*b.x[i]%MOD+MOD)%MOD;
tmp.dft(-1);
for(int i=0;i<nx;i++)b.x[i]=tmp.x[i],b.x[i+nx]=0;
}
}

void work(int *val,ll *tar,int sz,int ori)
{
init(2);
for(int i=0;i<sz;i++)
{
up[i].resize();
dn[i].resize();
if(i<ori)up[i].x[0]=1;
dn[i].x[0]=1;
dn[i].x[1]=-val[i],qm(dn[i].x[1]);
}
for(int i=1;i<sz;i<<=1)
{
init(min(i<<2,sz<<1));
dl.resize();
dr.resize();
ul.resize();
ur.resize();
for(int j=0;j+i<sz;j+=(i<<1))
{
dl.reset();
dr.reset();
ul.reset();
ur.reset();
for(int k=0;k<(len>>1);k++)dl.x[k]=dn[j].x[k];
for(int k=0;k<(len>>1);k++)dr.x[k]=dn[j+i].x[k];
for(int k=0;k<(len>>1);k++)ul.x[k]=up[j].x[k];
for(int k=0;k<(len>>1);k++)ur.x[k]=up[j+i].x[k];
dn[j].resize();
up[j].resize();
dl.dft(1);
dr.dft(1);
ul.dft(1);
ur.dft(1);
for(int k=0;k<len;k++)dn[j].x[k]=dl.x[k]*dr.x[k]%MOD;
for(int k=0;k<len;k++)up[j].x[k]=(ul.x[k]*dr.x[k]+dl.x[k]*ur.x[k])%MOD;
dn[j].dft(-1);
up[j].dft(-1);
}
}

dv.resize();
tmp.resize();
get_inv(dn[0],dv,len>>1);

dv.dft(1);
up[0].dft(1);
for(int i=0;i<len;i++)tmp.x[i]=dv.x[i]*up[0].x[i]%MOD;
tmp.dft(-1);

for(int i=0;i<sz;i++)tar[i]=tmp.x[i];
}

void calc_ans()
{
init(max(max(n1,m),n2));
int slen=len;
work(A,EA,slen,n1);
work(B,EB,slen,n2);
init(slen*2);
f1.resize();
f2.resize();
for(int i=0;i<len>>1;i++)f1.x[i]=EA[i]*inv(fac[i])%MOD*inv(n1)%MOD,f2.x[i]=EB[i]*inv(fac[i])%MOD*inv(n2)%MOD;
f1.dft(1);
f2.dft(1);
for(int i=0;i<len;i++)f1.x[i]=f1.x[i]*f2.x[i]%MOD;
f1.dft(-1);
for(int i=1;i<m;i++)printf("%lld\n",f1.x[i]*fac[i]%MOD);putchar('\n');
}

void prework()
{
fac[0]=1;
for(int i=1;i<MX;i++)fac[i]=fac[i-1]*(ll)i%MOD;
for(int i=0;i<MX;i++)gp[i]=ksm(G,(MOD-1)>>i),gpi[i]=inv(gp[i]);
for(int w=1,i=1;w<MX;i++,w<<=1)
{
wi[i][0]=1;
wii[i][0]=1;
for(int j=1;j<w;j++)
{
wi[i][j]=wi[i][j-1]*gp[i]%MOD;
wii[i][j]=wii[i][j-1]*gpi[i]%MOD;
}
}
}

int main()
{
prework();
scanf("%d%d",&n1,&n2);
scanf("%d",&m);m++;
calc_ans();
return 0;
}

2 条评论

XZYQvQ · 2018年7月8日 10:31 下午

Do you like van♂游戏？

boshi · 2018年7月9日 1:11 下午

I like VAN 游 Shi*