xdoj1420(二项式反演+FFT) | qkoqhh

题目链接

http://acm.xidian.edu.cn/problem.php?id=1409

题解

解法一

公式推了挺久。。

设答案为 $f(k)$ ，那么有

$f(k)=\binom mk (\frac{k}{m})^n-\sum_{d=1}^{k-1}f(d)\binom{m-d}{k-d}\\ \sum_{d=0}^{k}f(d)\binom{m-d}{k-d}=\binom mk(\frac{k}{m})^n\\ \sum_{d=0}^{k}\binom{m-d}{k-d}(-1)^d(-1)^df(d) =\binom mk(\frac{k}{m})^n\\ (-1)^kf(k)=\sum_{d=0}^{k}\binom{m-d}{k-d}(-1)^d\binom md(\frac{d}{m})^n\\ f(k)=\frac{m!}{(m-k)!m^n} \sum_{d=0}^{k}\frac{(-1)^{k-d}}{(k-d)!}\frac{d^n}{d!}$

然后后面的和式可以用 $FFT$ 做，复杂度 $O(nlogn)$

解法二

这题还可以利用生成函数。。

设指数型生成函数 $G(x,z)=1+z(e^x-1)$ ，有

$\begin{aligned} G^n(x,z)=&(1+ze^x)^n \\=&\sum_k\binom nk z^k(e^x-1)^k \\=&\sum_k\binom nk z^k\sum_j \binom kj(-1)^{k-j}e^{jx} \\=&\sum_k\binom nk z^k\sum_j \binom kj(-1)^{k-j}\sum_i j^i\frac{x^i}{i!} \\=&\sum_k\sum_i\sum_j\binom nk\binom kj(-1)^{k-j}j^iz^k\frac{x^i}{i!} \end{aligned}$

那么，所需要的项为 $z^k\frac{x^m}{m!}$ ，其系数为

$\sum_j \binom nk \binom kj (-1)^{k-j}j^m =\frac{n!}{(n-k)!} \sum_j \frac{j^m}{j!}\frac{(-1)^{k-j}}{(k-j)!}$

这和上面的结果一样了

代码

/**
 *　　　　　　  　　┏┓　　 　┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　┃ 　
 * 　　　　　  　　┃　　　━　　 　┃
 * 　　　　　  　　┃　＞　　　＜　┃
 * 　　　　　  　　┃　　　　　　　┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */ 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid (x+y)/2
#define NM 400005
#define nm 300005
using namespace std;
const double pi=acos(-1);
const ll inf=998244353;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}



int n,m,rev[NM],_x;
ll a[NM],b[NM],inv[NM],invp[NM],p[NM],_t;
ll qpow(ll x,ll t){return t?qpow(sqr(x)%inf,t>>1)*(t&1?x:1ll)%inf:1ll;}

void fft(ll*a,int f){
    inc(i,0,n-1)if(i<rev[i])swap(a[i],a[rev[i]]);
    for(int k=1;k<n;k<<=1){
	ll t=qpow(3,(inf-1)/k/2);if(f==-1)t=qpow(t,inf-2);
	for(int i=0;i<n;i+=k<<1){
	    ll w=1;
	    for(int j=0;j<k;j++,w=w*t%inf){
		ll x=a[i+j],y=w*a[i+j+k]%inf;
		a[i+j]=(x+y)%inf;a[i+j+k]=(x-y+inf)%inf;
	    }
	}
    }
}

void plu(ll*a,ll*b){
    int bit=0;
    n=2*n-1;
    while(succ(bit)<n)bit++;n=succ(bit);
    inc(i,1,n-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    ll invn=qpow(n,inf-2);
    fft(a,1);fft(b,1);inc(i,0,n-1)a[i]*=b[i],a[i]%=inf;
    fft(a,-1);inc(i,0,n-1)a[i]*=invn,a[i]%=inf;
    n=_x;
}

int main(){
    n=1e5;p[1]=p[0]=invp[0]=inv[1]=invp[1]=1;
    inc(i,2,n)p[i]=p[i-1]*i%inf,inv[i]=inv[inf%i]*(inf-inf/i)%inf,invp[i]=invp[i-1]*inv[i]%inf;
    while(~scanf("%d%d",&m,&n)){
	mem(a);mem(b);
	_t=m;_x=n;
	inc(i,0,min(n,m))if(i&1)b[i]=inf-invp[i];else b[i]=invp[i];
	inc(i,1,min(n,m))a[i]=qpow(i,n)*invp[i]%inf;
	n=min(n,m);n++;
	plu(a,b);m=_t;_t=qpow(inv[m],_x);
	n=min(n,m);
	inc(i,1,n)a[i]=a[i]*p[m]%inf*invp[m-i]%inf*_t%inf;
	inc(i,1,n-1)printf("%lld ",a[i]);printf("%lld\n",a[n]);
    }
    return 0;
}