「2020-2021 集训队作业」Yet Another Permutation Problem

题目大意

对于一个初始为 \(1,2,\ldots n\) 的排列，每次操作为选择一个数放到开头或者结尾，求 \(k\) 次操作能够生成的排列数

对于 \(k=0,1,\ldots ,n-1\) 求解

\[ \ \]

模型转化

容易发现，对于一个排列，生成它的最小次数取决于中间保留段的长度

而保留段实际上是任何一个上升子段

设一个排列的最长上升子段为 \(l\) ，那么最少操作步骤就是 \(n-l\)

那么对于 \(k\) ，合法的序列就是存在一个长度 \(\ge n-k\) 的上升子段

存在不好算，改为计算任何一个上升子段 \(<n-k\) 的数量

为了便于描述，令下文的 \(k=n-k-1\)

\[ \ \]

生成函数构造

考虑一个序列是由若干上升段构成的，设一个长度为 \(l\) 的上升段的权值为 \([l\leq k]\)

那么排列的权值就是上升段权值之积

容易想到用 \(\text{EGF}\) 合并上升段，但是直接的统计，我们无法保证上升段之间无法拼接

假设我们确定了一个单位上升段的 \(\text{EGF}\) 为 \(G(x)\) ， \(\text{OGF}\) 为 \(F(x)\)

那么按照上面 \(\text{Naive}\) 的计算，上升段之间的合并为有序拼接，即 \(\displaystyle \sum_{i=0}G^i(x)=\frac{1}{1-G(x)}\)

容易发现，这样的计算，会导致一个长度为 \(l\) 的极长上升段被分解成若干小段

也就是被计算了 \(\displaystyle [x^l](\sum_{i=0}F^i(x))=[x^l]\frac{1}{1-F(x)}\) 次

在合法的计算中，我们希望， \([x^l]\frac{1}{1-F(x)}\) 恰好为权值 \([l\leq k]\)

也就是说，我们希望 \(\displaystyle \frac{1}{1-F(x)}=H(x)=\sum_{i=0}^kx^i=\frac{x^{k+1}-1}{x-1}\)

那么可以反向由 \(H(x)\) 构造出我们想要的 \(F(x)\) ，从而得到 \(G(x)\) ，再进行求解

\[ \ \]

答案计算

\(\displaystyle F(x)=1-\frac{1}{H(x)}=1-\frac{x-1}{x^{k+1}-1}=\frac{x-x^{k+1}}{1-x^{k+1}}\)

可以爆算得到 \(F(x)\) ，从而得到 \(G(x)\) ，然后暴力求逆就是 \(O(n^2)\)

优化：

\(1-x^{k+1}\) 的逆，只包含 \(\frac{n}{k+1}\) 项，所以 \(G(x)\) 只含 \(2\frac{n}{k+1}\) 项

即 \(\displaystyle F(x)=\sum_{d=0}x^{d(k+1)+1}-\sum_{d=1}x^{d(k+1)}\) ， \(G(x)\) 就是除一个阶乘

这样暴力求逆就是 \(O(n^2\ln n)\)

（不是你干嘛要真的求逆，直接进行 \(G(x)\) 的叠加就可以了）

const int N=1010;

int n,P,I[N],J[N];
ll qpow(ll x,ll k=P-2){
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
int F[N];

int main(){
	n=rd(),P=rd();
	rep(i,*J=1,n) J[i]=1ll*J[i-1]*i%P;
	I[n]=qpow(J[n]);
	drep(i,n,1) I[i-1]=1ll*I[i]*i%P;
	drep(k,n,1) {
		F[0]=1;
		rep(j,1,n) {
			F[j]=0;
			for(int d=1;d<=j;d+=k) F[j]=(F[j]+1ll*F[j-d]*I[d])%P;
			for(int d=k;d<=j;d+=k) F[j]=(F[j]-1ll*F[j-d]*I[d])%P;
		}
		printf("%d\n",int((1ll*(P+1-F[n])*J[n])%P));
	}
}