给定长度为 的排列 ,要对于 求出,有多少个长度为 的排列 满足 字典序比 小,且 ,其中 表示 最少可以划分成多少个区间,使得每个区间中的元素都是公差为 的等差数列。
答案对输入的 取模, 不一定是质数。
,。
首先考虑没有字典序限制,求所有 的排列的答案。设 表示恰好分成 段的方案数, 表示钦定分成 段的方案数,那么有:
那么问题变成了求 ,没有字典序限制显然是简单的,字典序限制可以枚举 和 的 来解决。那么设 分别表示未填入的数中 小的连续段个数,以及这样的数的个数; 类似,只是把 换成 。注意跨越 的连续段被归为 里。
那么 钦定分成 段的方案数就是:
这个式子的意思是枚举 中断开了 个位置, 中断开了 个位置,然后这些连续段中只有 个能当第一个,剩下 个乱选。
接下来考虑化简:
还有一种情况, 有可能能填入 然后和 组成一个连续段。这种情况钦定后面(包括 和 组成的那一段)有 段的方案数为:
每次都容斥显然不行,那么弄个 dp 把 钦定的情况也统计一下,最后一起累加进 容斥即可。
时间复杂度 。
代码如下:
// 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;
}