牛客7745C - 数学考试

链接：https://ac.nowcoder.com/acm/contest/7745/C 知识点：组合数学,容斥,计数DP 难度：紫

题意

求 $1\sim n1\sim n$ 的排列，有 $mm$ 个限制条件， 第 $ii$ 个限制条件表示前 $P[i]P[i]$ 个数不能是 $P[i]P[i]$ 的排列， 求符合要求的排列的个数。

思路

考虑线性容斥。

初步思路：

1. 假设 $P[i]=\{3,5,7\}P[i]=\backslash lbrace\; 3,5,7\; \backslash rbrace$

2. 前 $33$ 个数字 是 $33$ 的排列的方案数 $=3!=3!$ 那么整个数列 前 $33$ 个数字 不是 $33$ 的排列的方案数 $=n!-3!=n!-3!$

3. 前 $55$ 个数字 是 $55$ 的排列的方案数 $=5!=5!$ 那么整个数列 前 $55$ 个数字 不是 $55$ 的排列的方案数 $=n!-5!=n!-5!$ 那么整个数列 前 $55$ 个数字 既不是 $33$ 的排列 又不是 $55$ 的排列的方案数 $=n!-3!-5!=n!-3!-5!$ 吗？ 减多了。 减去5的阶乘的同时，多减了1，2，3出现在前3位的情况。 那么，减去5的阶乘之后，要把 1，2，3出现在前3位的情况加回来。

4. 继续延伸，我们接下来需要做的是：

减去 $7!7!$之后，要把“1,2,3出现在前3位”，和“1,2,3,4,5出现在前5位但1,2,3没同时出现在前3位”的情况加回来。

减去 $7!7!$之后，要把“1,2,3出现在前3位但1,2,3,4,5没有出现在前5位”，和“1,2,3,4,5出现在前5位但1,2,3没同时出现在前3位”的情况加回来。

以上两句话哪句对？

显然是第一句， 因为“1,2,3出现在前3位” 和 “1,2,3,4,5出现在前5位但1,2,3没同时出现在前3位” 已经是完全相互独立的了。

5. 最后，我们用 $dp[i]dp[i]$ 表示，前 $1\mathrm{～}P[i]1～P[i]$ 的数字同时出现在 $1\mathrm{～}P[i]1～P[i]$，但是前 1～i-1 的条件都满足，也就是说：

前 1～P[i] 的数字同时出现在 1～P[i] 但是 前 $P[1]P[1]$ 的数字没有同时出现在 $1\mathrm{～}P[1]1～P[1]$ 前 $P[2]P[2]$ 的数字没有同时出现在 $1\mathrm{～}P[2]1～P[2]$ 前 $P[3]P[3]$ 的数字没有同时出现在 $1\mathrm{～}P[3]1～P[3]$ ... 前 $P[i-1]P[i-1]$ 的数字没有同时出现在 $1\mathrm{～}P[i-1]1～P[i-1]$

$dp[i]=i!-{\sum }_{j=\mathrm{1...}i-1}dp[j]\ast (i-j)!dp[i]=i!-\backslash sum\_\{j=1...i-1\}\{dp[j]*(i-j)!\}$ $sum+=dp[i]\ast (n-i)!sum+=dp[i]*(n-i)!$

6. $ans=n!-sumans=n!-sum$

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#define int long long
const int N	= 3010;
const int MOD	= 20000311;
using namespace std;

int bin[N];
int P[N];
int dp[N];
int n, m;

void Init()
{
	bin[0] = 1;
	for (int i=1; i<N; i++)
	{
		bin[i] = bin[i-1] * i, bin[i]%=MOD;
	}
}

void Solve()
{
	if(m==0)
	{
		printf("%lld\n",bin[n]);
		return;
	}
	
	int ans = bin[n];
	sort(P+1, P+1+m);
	for (int i=1; i<=m; i++)
	{
		dp[i] = bin[ P[i] ];
		for (int j=1; j<=i-1; j++)
		{
			dp[i] -= ( dp[j] * bin[ P[i] - P[j] ] ) % MOD;
			dp[i] = ( dp[i]+MOD ) % MOD;
		}
		ans -= (dp[i] * bin[ n-P[i] ])%MOD;
		ans = (ans+MOD)%MOD;
	}
	
	printf("%lld\n",ans);
}

signed main()
{
	Init();
	scanf("%lld %lld",&n,&m);
	for (int i=1; i<=m; i++)
	{
		scanf("%lld",&P[i]);
	}
	Solve();
	
	return 0;
}