39 条题解

  • 0
    @ 2015-12-14 23:39:18

    这题的关键要注意性质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;
    }

  • 0
    @ 2009-11-06 09:47:57

    Flag    Accepted

    题号   P1413

    类型(?)   数论 / 数值

    通过   300人

    提交   565次

    通过率   53%

    难度   1

    第300个^.^

    Orz 楼下数学大牛。

  • 0
    @ 2009-11-02 21:38:27

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

  • 0
    @ 2009-10-11 20:33:55

    撒花~~~

    提交300次...

  • 0
    @ 2009-09-23 20:18:50

    AC好爽

    数学太烂了

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

  • 0
    @ 2009-08-19 16:26:55

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

    AC 200 题!!!!!!

    纪念一下吧。

  • 0
    @ 2009-08-05 01:39:36

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

    实际上,最重要的是不断求余!!!!!

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

  • 0
    @ 2009-08-04 23:59:12

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

  • 0
    @ 2009-05-30 21:54:15

    排列组合吧。

    先从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。

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

  • 0
    @ 2009-03-28 14:16:53

    第三十题

    虽然是水题

    纪念一下

  • 0
    @ 2009-03-27 12:41:45

    穷举数字打错了

    两次才AC

    汗死了

  • 0
    @ 2009-02-27 20:01:27

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

  • 0
    @ 2009-02-21 19:32:36

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

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

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

  • 0
    @ 2009-01-17 09:32:56

    o(1)

  • 0
    @ 2008-11-13 18:52:21

    #include

    using namespace std;

    int main()

    {int i;

    cin>>i;

    if(i==1)cout

  • 0
    @ 2008-11-12 09:26:25

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

  • 0
    @ 2008-11-08 12:02:28

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

  • 0
    @ 2008-11-08 09:09:07

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

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

    先抢一楼 ._.

  • 0
    @ 2008-11-05 10:13:45

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-10-16 16:10:33

    无奈的程序..- -

信息

ID
1413
难度
3
分类
组合数学 点击显示
标签
递交数
384
已通过
201
通过率
52%
被复制
2
上传者