自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:24:47，当前版本为作者最后更新于2021-10-22 22:39:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

有 $n$ 个不同的人和 $n$ 道不同的题。

第 $i$ 个人开心当且仅当他被分配到 $i$ 道题。

求让至少一个人开心的分配方案数。

思路

显然 dp。

设 $f(i,j)$ 表示前 $i$ 个人分配 $j$ 道题且至少已经有一个人开心的方案数。

考虑转移：

• 使 $i$ 开心：随便給他 $i$ 道，剩下 $j-i$ 道随便分給剩下的 $i-1$ 个人。 方案数：$C(j,i)\times (i-1)^{j-i}$。

• 使 $i$ 不开心：随便給他 $k$ 道，剩下 $j-k$ 道給 $i-1$ 个人并使这 $i-1$ 个人中有人开心。 方案数：$C(j,k)\times f(i-1,j-k)$。

官方题解也是这种思路。

$code$

#include<stdio.h>
#define N 351
#define mod 1000000007
int n,c[N][N],ans[N][N];
inline int ksm(long long a,int b)
{
	long long ans=1;
	for(;b;b>>=1,a*=a,a%=mod)if(b&1)ans*=a,ans%=mod;
	return ans;
}
main()
{
	scanf("%d",&n);
	for(int i=0;i<=n;++i)
	{
		c[i][0]=c[i][i]=1;
		for(int j=1;j<i;++j)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	ans[1][1]=1;
	for(int i=2;i<=n;++i)for(int j=1;j<=n;++j)
	{
		if(j>=i)ans[i][j]=1ll*c[j][i]*ksm(i-1,j-i)%mod;//使i开心
		for(int k=0;k<=j;++k)if(i!=k)//使i不开心
			ans[i][j]=(ans[i][j]+1ll*ans[i-1][j-k]*c[j][k])%mod;
	}
	printf("%d",ans[n][n]);
}