专栏首页小L的魔法馆2018 Wannafly summer camp Day3--Travel

2018 Wannafly summer camp Day3--Travel

Travel 描述 题目描述: 魔方国有n座城市,编号为1∼n1∼n1\sim n。城市之间通过n-1条无向道路连接,形成一个树形结构。

澜澜打算在魔方国进行m次旅游,每次游览至少一座城市。为了方便,每次旅游游览的城市必须是连通的。此外,澜澜希望游览所有城市恰好一次。

澜澜想知道有多少种旅游方案满足条件,两个方案不同当且仅当存在某一次旅游游览了不同的城市。

澜澜不会数数,所以只好让你来帮他数方案。 输入: 第一行一个整数t表示数据组数 (1≤t≤100)(1≤t≤100)(1\leq t\leq 100)。 每组数据第一行两个整数n,m(1≤m≤n≤105,Σn≤106)(1≤m≤n≤105,Σn≤106)(1\leq m\leq n\leq 10^5,\Sigma{n}\leq 10^6),接下来n−1n−1n-1行每行两个整数ai,bi,ai​,bi​ai,bi,ai​,bi​a_i,b_i,ai​,bi​表示一条道路 (1≤ai,bi≤n)(1≤ai,bi≤n)(1\leq a_i,b_i\leq n)。 输出: 每组数据输出一行一个整数表示方案数对109+7109+710^9+7取模的结果。

样例输入 2 3 1 1 2 1 3 3 2 1 2 1 3 样例输出 1 4

  • 一开始看的时候,以为是图论,后面发现其实不是,这里的边其实并没有实际作用。因为题目只是要求在m次旅游中将n个城市都游历玩即可,所以用m-1条边将这个树划分为m个区域,这就代表了m次旅游,然后求其全排列就是答案 所以最终答案C(n-1,m-1)*m!
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn = 1 << 20;
const int mod = 1000000007;
int t, n, m, ta, tb;
ll c[maxn];
ll PowerMod(ll a, ll b, ll c) {
    ll ans = 1;
    a = a % c;
    while (b>0) {
        if (b % 2 == 1)
            ans = (ans * a) % c;
        b = b / 2;
        a = (a * a) % c;
    }
    return ans;
}
void init(){//先打出阶乘,节省时间
    c[1] = 1;
    for (int i = 2; i <= maxn; i++)
    {
        c[i] = c[i - 1] * i%mod; 
    }
}
ll C(ll n, ll m){return c[n] * PowerMod(c[m] * c[n - m] % mod, mod - 2, mod) % mod;}
int main(void) {
    scanf("%d", &t);
    init();
    while (t-- >0 ) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n - 1; i++)
            scanf("%d%d",&ta,&tb);
        if (m == 1) {
            printf("1\n");
            continue;
        }
        ll ans = C(n - 1, m - 1);
        ans = (ans*c[m]) % mod;
        cout << ans << endl;
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数学原来这么有趣,66组超炫动图唤醒你的思维!

    无论怎样,看完这一组动图,你不仅能够感受到数学美丽的一面,同时也会对我们常见的公式定理有更深刻、直观的理解!

    华章科技
  • 创业者注意了!大数据教你如何在众筹网站上成功融资

    有好点子,想创业,但没钱,怎么办?Kickstarter是美国著名的众筹网站,在这里可以帮有好点子的创业者实现梦想!本文数据侠抓取了Kickstarter的众筹...

    DT数据侠
  • EM Algorithm

    EM算法和之前学的都不太一样,EM算法更多的是一种思想,所以后面用几个例子讲解,同时也会重点讲解GMM高斯混合模型。

    西红柿炒鸡蛋
  • 【CVPR2018最佳论文提名】Deep Learning of Graph Matching论文解读

    作为一种常用的图数据处理技术,图匹配在计算机视觉中拥有丰富的应用场景和研究价值。CVPR2018最佳论文提名的工作Deep Learning of Graph ...

    SIGAI学习与实践平台
  • 来聊一聊 Spring 框架的前生今世

    这里的 Pivotal 团队肯定就是 Spring Boot 的研发团队了,那么这个 Pivotal 团队到底是个什么来头呢?和 Spring 又有那些关系?不...

    美码师
  • Codeforces Good Bye 2018 D (1091D)

    题目:New Year and the Permutation Concatenation

    ACM算法日常
  • BAT 经典算法笔试题: 镜像二叉树

    再过不到 2 个月,互联网行业就要再次迎来面试高峰了。为了让大家能顺利通过所有面试环节必经的笔试阶段,我提前给大伙准备了一套常见的算法笔试题。这套算法题来源于 ...

    老钱
  • 鸿篇巨制 —— LevelDB 的整体架构

    本节信息量很大,我们要从整体上把握 LevelDB 这座大厦的结构。当我们熟悉了整体的结构,接下来就可以各个击破来细致了解它的各种微妙的细节了。

    老钱
  • 网易云音乐为什么这么懂你?

    相信大家这几天的朋友圈已经被网易云音乐的年度听歌报告给刷屏了吧!不知道你们2018的年度关键词是什么,我的关键词是“青春”。

    谭庆波
  • BAT 经典算法笔试题 —— 逆转单向链表

    不善言谈的优秀程序员在面试中往往是要吃巨亏的,你没有办法通过说话来轻易证明自己的实力。不论是大厂还是小厂,大部分面试官都不具备优秀的面试能力,它们也只能通过三言...

    老钱

扫码关注云+社区

领取腾讯云代金券