vijosP1413 Valentine’s Present
【思路】
组合公式。
由题目知：每个箱子中的蛋糕要么与箱子颜色相同，要么指向一个蛋糕与箱子颜色相同的箱子。先从n个箱子中选取i个作为指向自己（箱子蛋糕颜色相同）的箱子，数目为C(n,i)，剩下的n-i个箱子每个箱子有i个选择所以方案数为i^(n-i)，总的方案数为C(n,i)*i^(n-i)，枚举i计和即可。
【代码】
#include<iostream>
using namespace std; int n;
long long C[][];
int MOD=; int main() {
cin>>n;
for(int i=;i<=n;i++) {
C[i][]=C[i][i]=;
for(int j=;j<i;j++) C[i][j]=(C[i-][j]+C[i-][j-])%MOD;
}
int ans=;
for(int i=;i<=n;i++) {
int tmp=;
for(int j=;j<=n-i;j++) tmp=tmp*i%MOD;
ans = (ans+C[n][i]*tmp%MOD)%MOD;
}
cout<<ans;
return ;
}