vijosP1413 Valentine’s Present

vijosP1413 Valentine’s Present

链接:https://vijos.org/p/1413

【思路】

  组合公式。

  由题目知:每个箱子中的蛋糕要么与箱子颜色相同,要么指向一个蛋糕与箱子颜色相同的箱子。先从n个箱子中选取i个作为指向自己(箱子蛋糕颜色相同)的箱子,数目为C(n,i),剩下的n-i个箱子每个箱子有i个选择所以方案数为i^(n-i),总的方案数为C(n,i)*i^(n-i),枚举i计和即可。

 【代码】

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int n;
 5 long long C[30][30];
 6 int MOD=19900801;
 7 
 8 int main() {
 9     cin>>n;
10     for(int i=1;i<=n;i++) {
11         C[i][0]=C[i][i]=1;
12       for(int j=1;j<i;j++)  C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
13     }
14     int ans=0;
15     for(int i=1;i<=n;i++) {
16        int tmp=1;
17        for(int j=1;j<=n-i;j++) tmp=tmp*i%MOD;
18        ans = (ans+C[n][i]*tmp%MOD)%MOD;
19     }
20     cout<<ans;
21     return 0;
22 }
原文地址:https://www.cnblogs.com/lidaxin/p/4876371.html