CF1750G Doping 做题记录

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

答案对输入的 $m$ 取模，$m$ 不一定是质数。

$n\le 2000$，$10\le m\le 10^9$。

首先考虑没有字典序限制，求所有 $n$ 的排列的答案。设 $f_{i}$ 表示恰好分成 $i$ 段的方案数，$g_i$ 表示钦定分成 $i$ 段的方案数，那么有：

$g_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}$

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

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

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

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

接下来考虑化简：

$\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}$

还有一种情况，$p'_i$ 有可能能填入 $p_{i-1}+1$ 然后和 $p'_{i-1}$ 组成一个连续段。这种情况钦定后面（包括 $p'_{i-1}$ 和 $p'_i$ 组成的那一段）有 $k$ 段的方案数为：

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

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

时间复杂度 $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;
}