CF1750G Doping 做题记录

给定长度为 nn 的排列 pp,要对于 k=1,2,3,,nk=1,2,3,\cdots,n 求出,有多少个长度为 nn 的排列 pp' 满足 pp' 字典序比 pp 小,且 f(p)=kf(p')=k,其中 f(a)f(a) 表示 aa 最少可以划分成多少个区间,使得每个区间中的元素都是公差为 11 的等差数列。

答案对输入的 mm 取模,mm 不一定是质数。

n2000n\le 200010m10910\le m\le 10^9

首先考虑没有字典序限制,求所有 nn 的排列的答案。设 fif_{i} 表示恰好分成 ii 段的方案数,gig_i 表示钦定分成 ii 段的方案数,那么有:

gi=j=1i(njij)fjfi=gij=1i1(njij)fjg_i=\sum\limits_{j=1}^{i}\binom{n-j}{i-j}f_j\\ f_i=g_i-\sum\limits_{j=1}^{i-1}\binom{n-j}{i-j}f_{j}

那么问题变成了求 gig_i,没有字典序限制显然是简单的,字典序限制可以枚举 pppp'lcp=i1\operatorname{lcp}=i-1 来解决。那么设 (ct1,tt1+ct1)(ct1,tt1+ct1) 分别表示未填入的数中 <pi<p_{i} 小的连续段个数,以及这样的数的个数;(ct2,tt2+ct2)(ct2,tt2+ct2) 类似,只是把 <pi<p_i 换成 pi\ge p_i。注意跨越 pip_i 的连续段被归为 (ct1,tt1+ct1)(ct1,tt1+ct1) 里。

那么 p[i,n]p'_{[i,n]} 钦定分成 kk 段的方案数就是:

j=0kct1ct2(ct1+j)(k1)!(tt1j)(tt2kct1ct2j)\sum\limits_{j=0}^{k-ct1-ct2}(ct1+j)(k-1)!\binom{tt1}{j}\binom{tt2}{k-ct1-ct2-j}

这个式子的意思是枚举 <pi<p_i 中断开了 jj 个位置,pi\ge p_i 中断开了 kct1ct2jk-ct1-ct2-j 个位置,然后这些连续段中只有 ct1+jct1+j 个能当第一个,剩下 k1k-1 个乱选。

接下来考虑化简:

j=0kct1ct2(ct1+j)(k1)!(tt1j)(tt2kct1ct2j)=(k1)!j=0kct1ct2(ct1(tt1j)+tt1(tt11j1))(tt2kct1ct2j)=(k1)!(ct1(tt1+tt2kct1ct2)+tt1(tt1+tt21kct1ct21))\begin{aligned} &\sum\limits_{j=0}^{k-ct1-ct2}(ct1+j)(k-1)!\binom{tt1}{j}\binom{tt2}{k-ct1-ct2-j}\\ &=(k-1)!\sum\limits_{j=0}^{k-ct1-ct2}\left(ct1\binom{tt1}{j}+tt1\binom{tt1-1}{j-1}\right)\binom{tt2}{k-ct1-ct2-j}\\ &=(k-1)!\left(ct1\binom{tt1+tt2}{k-ct1-ct2}+tt1\binom{tt1+tt2-1}{k-ct1-ct2-1}\right) \end{aligned}

还有一种情况,pip'_i 有可能能填入 pi1+1p_{i-1}+1 然后和 pi1p'_{i-1} 组成一个连续段。这种情况钦定后面(包括 pi1p'_{i-1}pip'_i 组成的那一段)有 kk 段的方案数为:

(k1)!(tt1+tt2kct1ct2)(k-1)!\binom{tt1+tt2}{k-ct1-ct2}

每次都容斥显然不行,那么弄个 dp 把 p[1,i1]p'_{[1,i-1]} 钦定的情况也统计一下,最后一起累加进 gg 容斥即可。

时间复杂度 O(n2)O(n^2)

代码如下:

// Problem: Doping
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1750G
// Memory Limit: 500 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>

using namespace std;

const int S=2005;

int n,p;
int a[S],C[S][S],fra[S];
bool vis[S],flg[S];
int dp[S][S];
int g[S],f[S];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline int qc(int n,int m)
{
	if(n<m||n<0||m<0) return 0;
	return C[n][m];
}

int main()
{
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=0;i<=S-3;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
	}
	fra[0]=1;
	for(int i=1;i<=S-3;i++) fra[i]=1ll*fra[i-1]*i%p;
	a[0]=-1;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) flg[j]=false;
		int ct1=0,tt1=0,ct2=0,tt2=0;
		for(int j=1;j<a[i];j++)
		{
			if(vis[j]) continue;
			if(flg[j-1]) tt1++;
			else ct1++;
			flg[j]=true;
		}
		for(int j=a[i];j<=n;j++)
		{
			if(vis[j]) continue;
			if(flg[j-1]) tt2++;
			else ct2++;
			flg[j]=true;
		}
		for(int k=ct1+ct2;k<=n-cnt;k++)
		{
			add(dp[i][cnt+k],1ll*fra[k-1]*(1ll*ct1*qc(tt1+tt2,k-ct1-ct2)%p+1ll*tt1*qc(tt1+tt2-1,k-ct1-ct2-1)%p)%p);
		}
		if(a[i-1]+1>=1&&a[i-1]+1<=n&&!vis[a[i-1]+1]&&a[i-1]+1<a[i])
		{
			for(int k=ct1+ct2;k<=n-cnt+1;k++)
			{
				add(dp[i][cnt+k-1],1ll*fra[k-1]*qc(tt1+tt2,k-ct1-ct2)%p);
			}
		}
		vis[a[i]]=true;
		cnt+=a[i]!=a[i-1]+1;
	}
	for(int i=n;i>=2;i--)
	{
		for(int j=1;j<=n;j++)
		{
			add(dp[i-1][j],dp[i][j]);
			if(a[i-1]==a[i-2]+1&&j<n) add(dp[i-1][j+1],dp[i][j]);
		}
	}
	for(int i=1;i<=n;i++) g[i]=dp[1][i];
	for(int i=1;i<=n;i++)
	{
		f[i]=g[i];
		for(int j=1;j<=i-1;j++)
		{
			add(f[i],p-1ll*qc(n-j,i-j)*f[j]%p);
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",f[i]);
	printf("\n");
	return 0;
}