【牛客练习赛71C】数学考试

题目

题目链接：https://ac.nowcoder.com/acm/contest/7745/C
牛牛在树剖姐姐的数学考试里出了一个题，但是树剖姐姐不会做，于是她向您求助。
求 \(1\sim n\) 的排列，有 \(m\) 个限制条件，第 \(i\) 个限制条件 \(p_i\) 表示前 \(p_i\) 个数不能是 \(1\sim p_i\) 的排列，求符合要求的排列的个数。
答案对 20000311 取模。

思路

先将 \(p\) 从小到大排序。
设 \(f[i]\) 表示满足了第 \(i\) 个条件的方案数。枚举上一次满足的条件，考虑容斥。

\[f[i]=-\sum^{i-1}_{j=1}f[j]\times (p[i]-p[j])! \]

时间复杂度 \(O(m^2)\)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=2010,MOD=20000311;
int n,m,p[N];
ll f[N],fac[N];

int main()
{
	scanf("%d%d",&n,&m);
	fac[0]=1;
	for (int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%MOD;
	for (int i=1;i<=m;i++)
		scanf("%d",&p[i]);
	p[++m]=n; p[++m]=0; f[1]=1;
	sort(p+1,p+1+m);
	for (int i=1;i<=m;i++)
		for (int j=1;j<i;j++)
			f[i]=(f[i]-f[j]*fac[p[i]-p[j]])%MOD;
	printf("%lld",(-f[m]%MOD+MOD)%MOD);
	return 0;
}