题解【P6870 [COCI2019-2020#5] Zapina】

_•́へ•́╬_ · 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]);
}