「Luogu5395」【模板】第二类斯特林数·行

problem

Solution

一句话题意：求i=0n{ni}_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}

根据第二类斯特林数的展开式，有

{nk}=1k!∑i=0k(−1)i(ki)(k−i)n\begin{Bmatrix}n\\k\end{Bmatrix}=\frac{1}{k!}\sum_{i=0}^k(-1)^i\begin{pmatrix}k\\i\end{pmatrix}(k-i)^n

具体证明可以看这里

进一步整理，式子化为

{nk}=∑i=0k(−1)ii!×(k−i)n(k−i)!\begin{Bmatrix}n\\k\end{Bmatrix}=\sum_{i=0}^k\frac{(-1)^i}{i!}\times \frac{(k-i)^n}{(k-i)!}

可以发现这是一个卷积的形式

构造多项式

F(x)=∑i=0n(−1)ii!xiF(x)=\sum_{i=0}^n\frac{(-1)^i}{i!}x^i

G(x)=∑i=0nini!xiG(x)=\sum_{i=0}^n\frac{i^n}{i!}x^i

S(x)=F(x)∗G(x)S(x)=F(x)*G(x)

则S(x)S(x)的kk次项系数即为{nk}\begin{Bmatrix}n\\k\end{Bmatrix}

预处理阶乘的逆元

本题的模数有原根33，所以直接用NTTNTT做卷积就可以了

时间复杂度O(nlog⁡n)O(n\log n)

Code

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
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#define inv(x) (fastpow((x),mod-2))
using namespace std;
typedef long long ll;

const int maxn=200005;
const ll mod=167772161,g=3,ig=55924054;
int n;
ll a[maxn<<2],b[maxn<<2],ifac[maxn];

ll fastpow(ll a,ll b)
{
	ll re=1,base=a;
	while(b)
	{
		if(b&1)
			re=re*base%mod;
		base=base*base%mod;
		b>>=1;
	}
	return re;
}

int len;
int rev[maxn<<2];

void NTT(ll *f,int type)
{
	for(register int i=0;i<len;++i)
		if(i<rev[i])
			swap(f[i],f[rev[i]]);
	for(register int p=2;p<=len;p<<=1)
	{
		int length=p>>1;
		ll unr=fastpow(type==1?g:ig,(mod-1)/p);
		for(register int l=0;l<len;l+=p)
		{
			ll w=1;
			for(register int i=l;i<l+length;++i,w=w*unr%mod)
			{
				ll tt=f[i+length]*w%mod;
				f[i+length]=(f[i]-tt+mod)%mod;
				f[i]=(f[i]+tt)%mod;
			}
		}
	}
	if(type==-1)
	{
		ll ilen=inv(len);
		for(register int i=0;i<len;++i)
			f[i]=f[i]*ilen%mod;
	}
}

int main()
{
	scanf("%d",&n);
	ifac[0]=1;
	for(register ll i=1;i<=n;++i)
		ifac[i]=ifac[i-1]*i%mod;
	ifac[n]=inv(ifac[n]);
	for(register ll i=n-1;i;--i)
		ifac[i]=ifac[i+1]*(i+1)%mod;
	for(register int i=0,o=1;i<=n;++i,o=mod-o)
		a[i]=o*ifac[i]%mod,b[i]=fastpow(i,n)*ifac[i]%mod;
	for(len=1;len<=n+n;len<<=1);
	for(register int i=1;i<len;++i)
		rev[i]=(rev[i>>1]>>1)|((i&1)?(len>>1):0);
	NTT(a,1);
	NTT(b,1);
	for(register int i=0;i<len;++i)
		a[i]=a[i]*b[i]%mod;
	NTT(a,-1);
	for(register int i=0;i<=n;++i)
		printf("%lld ",a[i]);
}