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

problem

Solution

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

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

\[\begin{Bmatrix}n\\k\end{Bmatrix}=\frac{1}{k!}\sum_{i=0}^k(-1)^i\begin{pmatrix}k\\i\end{pmatrix}(k-i)^n \]

具体证明可以看

进一步整理，式子化为

\[\begin{Bmatrix}n\\k\end{Bmatrix}=\sum_{i=0}^k\frac{(-1)^i}{i!}\times \frac{(k-i)^n}{(k-i)!} \]

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

构造多项式

\[F(x)=\sum_{i=0}^n\frac{(-1)^i}{i!}x^i \]

\[G(x)=\sum_{i=0}^n\frac{i^n}{i!}x^i \]

\[S(x)=F(x)*G(x) \]

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

预处理阶乘的逆元

本题的模数有原根\(3\)，所以直接用\(NTT\)做卷积就可以了

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

Code

#include 
#include 
#include 
#include 
#include 
#include 
#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>1;
		ll unr=fastpow(type==1?g:ig,(mod-1)/p);
		for(register int l=0;l>1]>>1)|((i&1)?(len>>1):0);
	NTT(a,1);
	NTT(b,1);
	for(register int i=0;i