文档章节

讲题

YYQ_ZJL
 YYQ_ZJL
发布于 2016/07/03 10:34
字数 325
阅读 4
收藏 0
#include <stdio.h>
#define maxn 1005
#define mod 1000000007
int cas,t = 1,road[maxn][maxn],n,k,ra,rb;
long long A[maxn],dp[maxn][maxn],size[maxn],ans;       /*dp[i][j]表示从1到i节点有j个节点是其字数的最大值*/
void init()
{
    int i,j;
    A[0] = 1;
    for(i = 1;i < maxn;i ++)
    {
        A[i] =  A[i-1] * i % mod;
    }
}
void init1()
{
    int i,j;
    for(i = 1;i <= n;i ++)
    {
        size[i] = 1;
        for(j = 1;j <= n;j ++)
            dp[i][j] = road[i][j] = 0;
    }
}
long long fast_pow(long long x, int n) {
    long long ret = 1;
    while (n) {
        if (n&1) ret = ret * x % mod;
        n >>= 1;
        x = x * x % mod;
    }
    return ret;
}

long long inv(long long x) {
    return fast_pow(x, mod-2);
}

/*得到以每个点为根的子树的节点数*/
void LookRoad(int r)
{
    int i;
    for(i = 1;i <= n;i ++)
    {
        if(road[r][i])
        {
            road[r][i] = road[i][r] = 0;
            LookRoad(i);
            size[r] += size[i];
        }
    }
}
int main()
{
    int i,j;
    long long p,q;
    scanf("%d",&cas);
    init();
    while(cas --)
    {
        scanf("%d %d",&n,&k);
        init1();
        for(i = 1;i < n;i ++)
        {
            scanf("%d %d",&ra,&rb);
            road[ra][rb] = road[rb][ra] = 1;
        }
        LookRoad(1);
        /*逆元代替分数*/
        dp[0][0] = 1;
        dp[0][1] = 0;
        for(i = 1;i <= n;i ++)
        {
            p = inv(size[i]);                                     /*该点是最大点的概率*/
            q = (size[i]-1)*p%mod;                                /*该点不是最大点的概率*/
            dp[i][0] = dp[i-1][0] * q % mod;
            for(j = 1;j <= i;j ++)
            {
                    dp[i][j] = (dp[i-1][j-1]*p%mod + dp[i-1][j]*q%mod)%mod;
            }
        }
        ans = dp[n][k] * A[n] % mod;
        printf("Case #%d: %lld\n",t++,ans);
    }
    return 0;
}

 

本文转载自:http://www.cnblogs.com/zhangjialu2015/p/5315154.html

YYQ_ZJL
粉丝 0
博文 30
码字总数 206
作品 0
杭州
其他
私信 提问
Vijos1984 随机树

题目传送门 突然听说要去THUAC让我很虚于是进入赛季恢复期 发现自己已经不如退役选手了。。。。No! 好的开始讲题 第一问:显然线性可加乱搞啊,f[i]表示n=i时候的答案 那么每加入2个节点在减...

JacaJava
2017/12/23
0
0
2018安卓巴士·深圳站 全球开发者论坛 【安卓开发者的修炼之道】

2018安卓巴士全球开发者论坛——安卓开发者的修炼之道 5月5日 · 深圳站 主办方:安卓巴士(中国最大的安卓开发者社区 http://www.apkbus.com) 活动介绍 安卓巴士,作为中国最大的安卓开发者...

安卓巴士
2018/04/17
8
0
2018年度OSC源创会计划,不能错过的技术分享大会

OSC 源创会是开源中国主办的面向开发者的线下技术分享和交流活动,目前已经举办了 7 年,覆盖全国一,二线IT主流城市,截止2018年2月举办次数已超过70场。源创会全部的图文回顾请浏览 https:...

OSC源创君
2018/03/01
7.9K
39
【叫板双11】18位技术大咖找你“约惠”喽!

关于全球敏捷运维峰会·上海站 2016年11月18日,全球敏捷运维峰会(Gdevops)将在上海带来本年度的收官之作,这将是一场集结技术先锋领袖与上千IT精英的顶尖盛会,也是一场萃取架构、敏捷、运...

DBAplus社群
2016/11/11
0
0
演讲的好处

演讲不仅是一种表达思想、与他人沟通的有用工具,同时也是一种思维的训练。胡适在自传中举了一个例子: 所有中国学生大致都知道或多或少有关儒教的教义,但是他们对儒教的了解多半流于空泛、...

阮一峰
2007/02/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

thinkphp5.1学习过程四——trait

<?php /** *trait实现了代码的复用 *并且突破了单继承的限制 *trait是类不是类,不能实例化 */ trait Demo1 { public function hello1() { return __METHOD__; } } trait Demo2 { public fu......

大海yht
29分钟前
6
0
DB2 sequence 操作

操作DB2 下 sequence seqName db2数据库一般seq还是比较大的,但是程序在调用的时候还是不可避免的有一些bug, 下面是对于seq一些简单的操作,也作为工作的一些记录 1、命令行取sequence se...

飞雪无痕
37分钟前
6
0
《吊打面试官》系列-秒杀系统设计

你知道的越多,你不知道的越多 点赞再看,养成习惯 GitHub上已经开源 https://github.com/JavaFamily 有一线大厂面试点脑图和个人联系方式,欢迎Star和指教 絮叨 之前写了很多Redis相关的知识...

敖丙
43分钟前
12
0
Qt编写气体安全管理系统11-数据打印

一、前言 在各种软件系统中,数据打印也是常用的功能之一,一般来说会对查询的数据结果导出到excel,还会对查询的数据结果直接打印,在Qt中提供了打印机类QPrinter,在printsupport组件中,可...

飞扬青云
49分钟前
5
0
初级阶段

#include <stdio.h> #include <stdlib.h> int main(){ int a; int Sn = 0; int i; int tmp = 0; scanf_s("%d", &a); for (i = 1; i <= 5; i++) { tmp = tmp * 10 + a; Sn += tmp; } printf("......

Lxxxxx256
50分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部