牛客网 - [北京信息科技大学第十一届程序设计竞赛]kotori和气球(排列组合)
发布日期:2021-07-01 00:18:54
浏览次数:2
分类:技术文章
本文共 799 字,大约阅读时间需要 2 分钟。
题目链接:
时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K 64bit IO Format: %lld题目描述
kotori最近迷上了摆气球的游戏。她一共有n种气球,每种气球有无数个。她要拿出若干个气球摆成一排。
但是,由于气球被施放了魔法,同样种类的气球如果相邻会发生爆炸,因此若两个相邻的气球种类相同被视为不合法的。 kotori想知道,摆成一排m个一共有多少种不同的方案? 由于该数可能过大,只需要输出其对109取模的结果。输入描述
输入仅有一行,为两个整数n和m(1≤n,m≤100)
输出描述
输出一个整数,为方案数对109取模的结果。
输入
3 2
输出
6
说明
假设3种气球标记为1、2、3,那么共有以下6种方案:[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]。
解题思路
题意:求满足要求的m个气球的排列数。
思路:组合数学,第1个有n种选择,则剩余的m-1个都只有n-1种选择,故总的排列数为。Accepted Code:
#includeusing namespace std;const int MOD = 109;int pow_(int a, int b) { int cnt = 1; while (b) { if (b & 1) cnt = cnt * a % MOD; b >>= 1; a = a * a % MOD; } return cnt;}int main() { int n, m; scanf("%d%d", &n, &m); printf("%d\n", pow_(n - 1, m - 1) * n % MOD); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/94548278 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月09日 00时39分34秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
膜拜!这份技术点拉满的Redis深度历险笔记,价值百万!
2019-05-01
RabbitMQ消息队列(七):适用于云计算集群的远程调用(RPC)
2019-05-01
xtrabackup备份之增量备份(二)
2019-05-01
《视频直播技术详解》系列:(6)编码和封装
2019-05-01
类函数重写、重载、覆盖示例
2019-05-01
五种主要多核并行编程方法分析与比较
2019-05-01
GB28181计算注册登陆时的鉴权信息
2019-05-01
人工智能为什么这么火?看看安防江湖30年血战就知道了
2019-05-01
“中国已建成世界上最大的视频监控网”背后的问题
2019-05-01
一个ps解复用H264和H264打包ps的动态库及demo
2019-05-01
“前端智能为安防产生新的数据价值”
2019-05-01
异或^ 的几个作用
2019-05-01
nanomsg编译与测试
2019-05-01
(2)CMake入门笔记--CMake官网教程
2019-05-01
(3)CMake入门笔记--CMake官网教程
2019-05-01
(4)CMake入门笔记--CMake官网教程
2019-05-01
(XWZ)的python学习笔记Ⅰ
2019-05-01
(XWZ)的Python学习笔记Ⅱ------面向对象编程
2019-05-01
(XWZ)的Python学习笔记Ⅲ——面向对象高级编程
2019-05-01
(XWZ)的python学习笔记Ⅳ——错误、调试和测试
2019-05-01