FPS24 题解

B - Tuple of Integers

\[[x^n](1+x)(1+x+x^2)(\frac1{1-x^2})(\frac1{1-x^3})\\ =[x^n]\frac1{(x-1)^2}=\binom{-2}ix^i(-1)^{-2-i}=n+1\]

D - Sequence 2

考虑去计算 B 的数量，由于每个数字互不相同，所以 A 的数量就是 B 的数量乘以 $n!$。
对于相邻奇偶性不同，实际上就是差分后的每个数都是奇数。
但是差分后会少了一个数，我们要根据差分数组的总和 $i$ 来确定第一个数有 $m-i+1$ 种取法。

\[F(x)=[x^m](x+x^3+x^5+\cdots)^{n-1}\\ \text{ans}=n!\sum_{i=0}^m F_i\times(m-i+1)\]

E - Sequence 3

\[\hat F_i(x)=\sum_{j=0}^i \frac{x^j}{j!}\\ \text{ans}=n!\times[x^n]\prod_{i=0}^m F_i(x)\]

F - Colored Paper

\[[x^n]e^x(\frac{e^x+e^{-x} }2)(\frac{e^x-e^{-x} }2)=[x^n]\frac{e^{3x}-e^{-x} }4=\frac{3^n-(-1)^n}4\]

G - Coin

\[\text{ans}_p=\prod_{i=p}^{p+l-1}\frac1{1-x^i}\]

需要手写背包，每次移动 $p$，加入一种物品，删除一种物品，复杂度 $\mathcal O(n^2)$。

F[0]=1;
for(int i=1;i<=l;i++){
	for(int j=i;j<=n;j++)F[j]+=F[j-i];
}
cout<<F[n]<<'\n';
for(int i=l+1;i<=m;i++){
	for(int j=i;j<=n;j++)F[j]+=F[j-i];
	for(int j=n;j>=i-l;j--)F[j]-=F[j-(i-l)];
	cout<<F[n]<<'\n';
}

H - Jump

枚举总步数 $i$，其中有 $n$ 步 $x$ 会 $+1$，其余 $i-n$ 步则不能走空。
此时相当于 $i$ 个数总和为 $m$，其中 $n$ 个数 $\ge0$，$i-n$ 个数 $>0$，插板法，答案就是

\[\sum_{i=n}^{n+m}\binom in\binom{m+n-1}{i-1}=\frac{2^{m-1}(m+2n)(n+m-1)!}{n!m!}\]

J - Sugoroku

不难写出转移方程

\[F_i=\frac1{m}\sum_{j-i\in A}F_j\]

这是半在线卷积，分治 NTT 即可。
为了避免边界，我在越界的地方塞了若干 $1$。
为了好写一点，我把整个数组倒过来了。

void solve(int l,int r){
	if(l==r){
		if(b[l]==2)F[l]=1;
		else if(b[l]==1)F[l]=0;
		else F[l]/=m;
		return;
	}
	solve(l,mid);
	if(mid+1>=n){
		poly t1(F.begin()+l,F.begin()+mid+1);
		poly t2(a,a+r-l+2);
		poly t3=t1*t2;
		for(int i=mid+1;i<=r;i++)
			F[i]+=t3[i-l];
	}
	solve(mid+1,r);
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n>>m>>q;
	for(int i=1,x;i<=m;i++)cin>>x,a[x]=1;
	for(int i=1,x;i<=q;i++)cin>>x,b[2*n+1-x]=1;
	F.resize(2*n+2);
	for(int i=1;i<=n+1;i++)b[i]=2;
	solve(1,2*n+1);
	cout<<F[2*n+1];
	return 0;
}

K - Permutation

\[F_n=\sum_{i=1}^n i!F_{n-i}\\ G(x)=\sum_{i=0}^\infty i!x^i\\ F=1+F*G\]

即

\[F(x)=1-\frac1{G(x)}\]

L - Permutation 2

按照置换环大小对生成函数进行分类，记 $F_n(x)$ 表示置换环大小为 $i$ 的指数生成函数，那么直接使用 $\exp$ 的组合意义，去考虑单个置换环的指数生成函数，可以直接得到

\[\hat F_n(x)=\exp(n-1)!\frac{x^n}{n!}=\exp\frac{x^n}n\\ \text{ans}=n!\times[x^n]\prod_{i=3}^n\exp\frac{x^n}n=n!\times[x^n]\exp\sum_{i=3}^n\frac{x^n}n\]

M - Connected Graph

不连通图是由若干联通图组成的，而不连通的指数生成函数就是乱连。

\[\hat G(x)=\sum_{i=0}^\infty 2^{\binom i2}\frac{x^i}{i!}\\ \text{ans}=n![x^n]\ln\hat G(x)\]

N - Coin 2

\[\text{ans}=[x^n]F(x)\\ F(x)=\prod_{i=1}^n(1+x^i+x^{2i}+\cdots+x^{a_ii})=\prod_{i=1}^n\frac{1-x^{(a_i+1)i}}{1-x^i}\\ \ln F(x)=\sum_{i=1}^n\left(\ln(1-x^{(a_i+1)i})-\ln(1-x^i)\right)\\\]

注意到 $\ln$ 内的项是调和级数数量级的，对 $\ln$ 泰勒展开后手动加减，最后 $\exp$ 回去就好了。

O - Rooted Tree

题目里限制了 $1$ 为根，不妨任意选定根最后再除以 $n$。

\[\hat F(x)=x(1+\sum_{i\in\mathbb P}\hat F^i(x))\]

发现解不出 $\hat F(x)$，不妨反表示一下然后拉反。

\[x=\frac{\hat F(x)}{(1+\sum_{i\in\mathbb P}\hat F^i(x))}\]

即 $\hat F(x)$ 的复合逆

\[\hat G(x)=\frac{x}{(1+\sum_{i\in\mathbb P}x^i)}\]

那么

\[[x^n]F(x)=\frac1n[x^{n-1}]\left(\frac x{G(x)}\right)^n\] \[\text{ans}=\frac1{n}n![x^n]F(x)\]

P - Ball

不妨枚举 $0$ 号盒子中球的数量 $i$。

\[\text{ans}_x=\sum_{i=0}^k\binom nix^{n-i}\]

然后多项式多点求值。

\[\begin{aligned} \mathbb E[(A+B)^k]&=\mathbb E\left[\sum_{i=0}^k\binom kiA^iB^{k-i}\right]\\ &=\sum_{i=0}^k\binom ni\mathbb E[A^i]\mathbb E[B^{k-i}] \end{aligned}\] \[\hat F(x)=\sum_{i=0}^k\left(\sum_{j=1}^na_j^i\right)\frac{x^i}{i!}\\ \hat G(x)=\sum_{i=0}^k\left(\sum_{j=1}^mb_j^i\right)\frac{x^i}{i!}\\\] \[\mathbb E[A^i]=\frac{F_i}n,\mathbb E[B^i]=\frac{G_i}m\\ \mathbb E[(A+B)^k]=k!\sum_{i=0}^k\hat F_i\hat G_{k-i}\frac1{nm}\]

现在只需求解 $\hat F(x),\hat G(x)$，不妨去计算其普通生成函数 $F(x),G(x)$，然后手动每项除以 $i!$。

\[\begin{aligned} F(x)&=\sum_{i=0}^k\left(\sum_{j=1}^na_j^i\right)x^i\\ &=\sum_{i=1}^n(1+a_ix+(a_ix)^2+\cdots)\\ &=\sum_{i=1}^n\frac1{1-a_ix} \end{aligned}\]

这里，可以使用分治 NTT 去处理分数多项式，分子分母分开存，每次合并是 $3$ 次卷积，常数较大。

更好的做法是注意到

\[H(x)=\frac1{\prod\limits_{i=1}^n(1-a_ix)}\\ n+\frac{xH'(x)}{H(x)}=F(x)\]