牛客5633D - 宝石装箱

• 链接：https://ac.nowcoder.com/acm/contest/5633/D
• 知识点：线性容斥、背包DP
• 难度：蓝

题意

• 将 $nn$ 个物品装进 $nn$ 个箱子，每个箱子恰好装一个物品。
• 要求第 $ii$ 个物品不能装入第 $a_{i}a\_i$ 个箱子中。
• 问有多少种合法的方案。

思路

错误思路

• 线性容斥。计算不合法的总方案数。$ans=n!-\mathrm{不}\mathrm{合}\mathrm{法}\mathrm{的}\mathrm{总}\mathrm{方}\mathrm{案}\mathrm{数}ans=n!-不合法的总方案数$
• $\mathrm{不}\mathrm{合}\mathrm{法}\mathrm{的}\mathrm{总}\mathrm{方}\mathrm{案}\mathrm{数}={\sum }_{i=1}^n\mathrm{前}i\mathrm{个}\mathrm{箱}\mathrm{子}\mathrm{合}\mathrm{法}\mathrm{且}\mathrm{第}i\mathrm{个}\mathrm{箱}\mathrm{子}\mathrm{不}\mathrm{合}\mathrm{法}\mathrm{的}\mathrm{方}\mathrm{案}\mathrm{数}不合法的总方案数=\backslash sum\_\{i=1\}^\{n\}前i个箱子合法且第i个箱子不合法的方案数$
• 上面这个表达式是正确的，但是 前i个箱子合法且第i个箱子不合法的方案数 太难算。

正确思路

• 线性容斥。
• 我们发现 至少有 $ii$ 个箱子不合法 好算
• 我们从至少有 $ii$ 个箱子不合法入手
• $dp[i]dp[i]$ 表示至少有 $ii$ 个箱子不合法
• $ans={\sum }_{i=1}^n[(-1{)}^i\times dp[i]\times (n-i)!]ans=\backslash sum\_\{i=1\}^\{n\}[(-1)^i\backslash times\; dp[i]\backslash times(n-i)!]$
• 如何计算 $dp[i]dp[i]$？
• 背包转移。

代码

#include <cstdio>
#include <iostream>
#define int long long
const int N		= 1e6+10;
const int MOD	= 998244353;
using namespace std;

int bin[N];
int cnti[N],dp[N];
int n;

void Solve()
{
	bin[0] = 1;
	for (int i=1; i<=n; i++)
	{
		bin[i] = bin[i-1]*i%MOD;
	}
	
	dp[0] = 1;
	for (int i=1; i<=n; i++)
	{
		if(!cnti[i])continue;
		
		for (int j=n; j>=1; j--)
		{
			dp[j] += dp[j-1]*cnti[i]%MOD, dp[j]%=MOD;
		}
	}
	
	int ans = 0;
	int base = -1;
	for (int i=0; i<=n; i++)
	{
		base *= -1;
		ans += (base * dp[i] * bin[n-i] + MOD) % MOD, ans+=MOD,ans%=MOD;
	}
	
	printf("%lld\n",ans);
}

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