「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)=[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));
	}
}