这题的关键要注意性质2："任意开启一个箱子，按里面蛋糕的颜色打开对应的箱子，这两个箱子（也可以是同一个）里的蛋糕颜色相同"。
我们借助一个图论模型来分析：将每个盒子看做一个点,颜色为i的盒子看成节点i，如果颜色为i的盒子中装了颜色为j的蛋糕，那么从i到j连一条有向边。显然，每个点的出度为1。
通过观察和分析发现，要满足性质2，如果i到j连了一条有向边(i!=j)，那么从j出发的有向边必定连到j(自环)。即颜色为j的盒子里装的蛋糕颜色也为j。
因此，我们可以根据满足【蛋糕与装这个蛋糕的盒子颜色不同】的蛋糕数量x分类，那么该部分的答案为C(n,x)*(n-x)^x。容易发现，x不同时，方案是必定不会相同的。那么根据加法原理，我们从0到n-1枚举x，所得的各部分方案总和即为答案
#include<cstdio>
const int mo=19900801;
int n;
long long ans,s,c,p;
long long pow(long long a,long long n){
p=1;
while (n){
if (n&1)
p=(p*a)%mo;
a=(a*a)%mo;
n>>=1;
}
return p;
}
int main(){
scanf("%d",&n);
if (n==1){
printf("1\n");
return 0;
}
ans=0;
c=1;
for (int i=0;i<n;i++){
s=(c*pow(n-i,i))%mo;
c=(c*(n-i))%mo;
c=(c*pow(i+1,mo-2))%mo;
ans=(ans+s)%mo;
}
printf("%lld\n",ans);
return 0;
}

Flag 　　 Accepted

题号 　　P1413

类型(?) 　　数论 / 数值

通过 　　300人

提交 　　565次

通过率 　　53%

难度 　　1

第300个^.^

Orz 楼下数学大牛。

由于范围小才25 完全打表自己把排列组合算下时间比穷举好的多...

撒花~~~

提交300次...

AC好爽

数学太烂了

C(n,i)*i^(n-i)

最好开int64，防止出现负数。

AC 200 题！！！！！！

纪念一下吧。

理论上ans=sigma(i from 1 to n){C(n,i)*(i^(n-i))}(没办法，式子只能写得这么丑了）

实际上，最重要的是不断求余！！！！！

还要注意在求余之前的计算不能超出范围

挺好的,必须有点排列组合的功夫呵呵~

排列组合吧。

先从1到n枚举有几个盒子的颜色是相同的，

在计算出n个盒子中k个盒子颜色相同的有几种，公式是sk=n*(n-1)*(n-2)*...*(n+1-k)/1/2/.../k。

再用乘法原理，剩余的n-k个每个必须和k个中的一个颜色一样，每种状态有tk=k*k..*k(n-k个k相乘种)

所以k个盒子颜色相同的情况为wk=sk*tk，

那么总和total=w1+w2+...+wn。

呼，第一次写的那么详细。

第三十题

虽然是水题

纪念一下

穷举数字打错了

两次才AC

汗死了

穷举万岁!!!!!!!!!!!!!!!!!!!!!

答案是把所有M从1到N,对C(N,M)*M^(N-M)求和取模.

其中 C(N,M)：从n各选m个指向自己 的方案数

M^(N-M)：剩下n-m个不指向自己的盒子，每个有m种选择，即总数为 M^(N-M)

o(1)

#include

using namespace std;

int main()

{int i;

cin>>i;

if(i==1)cout

Ans=∑C(N,P)*P^(N-P),1

楼上的……我不是故意的。。。

100th被 fammiebright　抢了 -_-||||||

就差一点...........

先抢一楼 ._.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

无奈的程序..- -