Codeforces 1528F - AmShZ Farm（转化+NTT+推式子+第二类斯特林数）

神仙题，只不过感觉有点强行二合一（？）。

首先考虑什么样的数组 \(a\) 符合条件，我们考虑一个贪心的思想，我们从前到后遍历，对于每一个 \(a_i\) 如果它已经在前面出现了就不断给它加 \(1\) 直到它没有出现过为止。如果某个 \(a_i\) 超过了 \(n\) 则不符合条件，正确性显然。这样看起来还是有点抽象，我们不妨把它转化成这样的模型：有一架飞机有 \(n\) 个位置，有 \(n\) 个乘客要登飞机，每个乘客都预定了一个位置 \(a_i\)，每个乘客上飞机的时候，如果它的位置已经被占了，那么它会一直向前走直到到达一个空位为止并坐下，如果有乘客没位置坐则不符合题意。

这是一个非常经典的问题，仿照那题的解法可以考虑这样的转化：添加一个 \(n+1\) 号位并接链成环（？），将原先在链上走转化为在环上走，那么 \(a\) 符合条件当且仅当 \(n+1\) 位置最后没有被占。由于这 \(n+1\) 个点组成一个环，故 \(n+1\) 个点是对称的，它们被占的概率都是相同的，为 \(\dfrac{1}{n+1}\)，因此合法的 \(a\) 的个数就是总序列数乘 \(\dfrac{1}{n+1}\)，即 \((n+1)^{n-1}\)（注意：这里我们要做一个微调，即将 \(a_i\) 的上界扩大到 \(n+1\)，否则就无法保证每个点都是对称的了，这个 \(\dfrac{1}{n+1}\) 也就不成立了，故总序列个数实际上是 \((n+1)^n\)，并且如果 \(\exists a_i=n+1\) 那么肯定就不合法了，因此你改就改呗，也不影响我合法的序列 \(a\) 的个数）。

到这里我们只分析完了序列 \(a\) 的性质，即将序列 \(a\) 的贡献全当作 \(1\) 来算后得到的答案，可实际上对于某个 \(a\) 它对答案的贡献并不是 \(1\)，而是 \(\sum\limits_{i=1}^{n+1}c_i^k\)，其中 \(c_i\) 为 \(i\) 的出现次数。这时候又到了动用咱们聪明才智的时候了。考虑继续分析 \(a\) 的性质，还是从「\(n+1\) 个点组成一个环」这个条件入手，显然我们将每个点都向右平移 \(C\) 格后每个数的出现次数不变，即合法的 \(b\) 的个数 \(cntb(a)\) 不变，但最后留下来的位置也会跟着平移 \(C\) 格。因此考虑对每个合法的序列 \(a\) 做 \(n\) 次映射，即 \(a_i:=(a_i+C-1)\bmod(n+1)+1\)，\(C=1,2,3,\cdots,n\)。由于 \(a\) 是合法的序列，故映射后的序列肯定不是合法序列，显然这 \(n+1\) 个序列的 \(cntb\) 都是相同的，又所有合法序列映射后肯定恰好包含全部序列，因此我们可以求出所有序列的答案之和后除以 \(n+1\) 即可算出答案。

接下来考虑怎么计算所有序列的答案之和，显然每个数的贡献都是相同的，计算出一个数的贡献后乘以 \(n+1\) 即为总贡献，又最后要除掉一个 \(n+1\)，他俩刚好怼调了。计算一个数的贡献还算好办，枚举出现次数排列组合求一下即可，即

\[\text{ans}=\sum\limits_{i=0}^n\dbinom{n}{i}i^kn^{n-i}
\]

接下来就是愉快地推式子环节了，至此我们进入了本题的第二部分：

\[\begin{aligned}
\text{ans}&=\sum\limits_{i=0}^n\dbinom{n}{i}i^kn^{n-i}
\\&=\sum\limits_{i=0}^n\dbinom{n}{i}n^{n-i}\sum\limits_{j=0}^i\begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{i}{j}&(\text{第二类斯特林数的性质})
\\&=\sum\limits_{i=0}^n\sum\limits_{j=0}^i\dbinom{n}{i}\dbinom{i}{j}n^{n-i}\begin{Bmatrix}k\\j\end{Bmatrix}j!
\\&=\sum\limits_{i=0}^n\sum\limits_{j=0}^i\dbinom{n}{j}\dbinom{n-j}{i-j}n^{n-i}\begin{Bmatrix}k\\j\end{Bmatrix}j!&(\text{吸收恒等式})
\\&=\sum\limits_{j=0}^n\dbinom{n}{j}\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits_{i=j}^n\dbinom{n-j}{i-j}n^{n-i}&(\text{交换求和号})
\\&=\sum\limits_{j=0}^n\dbinom{n}{j}\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits_{i=0}^{n-j}\dbinom{n-j}{i}n^{n-i-j}·1^i
\\&=\sum\limits_{j=0}^n\dbinom{n}{j}\begin{Bmatrix}k\\j\end{Bmatrix}j!(n+1)^{n-j}
\end{aligned}
\]

\(\begin{Bmatrix}k\\j\end{Bmatrix}\) 可以通过第二类斯特林数·行求出，于是这道二合一的缝合怪题终于做完了（

const int MAXP=1<<18;

const int MAXN=1e5;

const int pr=3;

const int MOD=998244353;

const int ipr=(MOD+1)/3;

int qpow(int x,int e){

	int ret=1;

	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;

	return ret;

}

int n,k,rev[MAXP+5],fac[MAXN+5],ifac[MAXN+5];

void init_fac(int n){

	for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;

	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;

}

void NTT(vector<int> &a,int len,int type){

	int lg=31-__builtin_clz(len);

	for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<lg-1);

	for(int i=0;i<len;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);

	for(int i=2;i<=len;i<<=1){

		int W=qpow((type<0)?ipr:pr,(MOD-1)/i);

		for(int j=0;j<len;j+=i){

			for(int k=0,w=1;k<(i>>1);k++,w=1ll*w*W%MOD){

				int X=a[j+k],Y=1ll*a[(i>>1)+j+k]*w%MOD;

				a[j+k]=(X+Y)%MOD;a[(i>>1)+j+k]=(X-Y+MOD)%MOD;

			}

		}

	}

	if(type==-1){

		int ivn=qpow(len,MOD-2);

		for(int i=0;i<len;i++) a[i]=1ll*a[i]*ivn%MOD;

	}

}

vector<int> conv(vector<int> a,vector<int> b){

	int LEN=1;while(LEN<a.size()+b.size()) LEN<<=1;

	a.resize(LEN,0);b.resize(LEN,0);NTT(a,LEN,1);NTT(b,LEN,1);

	for(int i=0;i<LEN;i++) a[i]=1ll*a[i]*b[i]%MOD;

	NTT(a,LEN,-1);return a;

}

int main(){

	scanf("%d%d",&n,&k);init_fac(k);

	vector<int> a(k+1),b(k+1);

	for(int i=0;i<=k;i++){

		a[i]=(i&1)?(MOD-ifac[i]):ifac[i];

		b[i]=1ll*qpow(i,k)*ifac[i]%MOD;

	} a=conv(a,b);int cur=1,ans=0;

	for(int j=1;j<=min(n,k);j++){

		cur=1ll*cur*(n-j+1)%MOD*qpow(j,MOD-2)%MOD;

		ans=(ans+1ll*a[j]*fac[j]%MOD*cur%MOD*qpow(n+1,n-j))%MOD;

	} printf("%d\n",ans);

	return 0;

}

巴特西

Codeforces 1528F - AmShZ Farm（转化+NTT+推式子+第二类斯特林数）

最新文章

热门文章