BZOJ1008: [HNOI2008]越狱(组合数)
2018-07-11 03:31:03来源:博客园 阅读 ()
题目描述
监狱有连续编号为 1…N1…N 的 NN 个房间,每个房间关押一个犯人,有 MM 种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱。
输入输出格式
输入格式:
输入两个整数 $M,N$
输出格式:
可能越狱的状态数,模 100003100003 取余
输入输出样例
2 3
6
说明
6种状态为(000)(001)(011)(100)(110)(111)
1 \le M \le 10^81≤M≤108
1 \le N \le 10^{12}1≤N≤1012
很zz的数数题。
发现直接数不好数,那就容斥一下吧,。
所有的情况是$M^N$,两两不能相邻,那么第一个可以选$M$个,第二个可以选$M - 1$个,以此类推都能选$M - 1$个
因此答案为$M^N - M * (N - 1)^{M - 1}$
#include<cstdio> #include<algorithm> #include<cmath> #include<map> #define int long long using namespace std; const int MAXN = 4 * 1e5 + 10, mod = 100003; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int M, N; int fastpow(int a, int p) { int base = 1; while(p) { if(p & 1) base = (base % mod * a % mod) % mod; a = (a % mod * a % mod) % mod; p >>= 1; } return base % mod; } main() { M = read(); N = read(); //M %= mod; N %= mod; printf("%lld", (fastpow(M, N) - (M % mod) * (fastpow(M - 1, N - 1)) % mod + mod) % mod); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
- 斜率优化dp学习笔记 洛谷P3915[HNOI2008]玩具装箱toy 2019-08-16
- BZOJ1004: [HNOI2008]Cards(Burnside引理 背包dp) 2018-07-12
- bzoj1008 [HNOI2008]越狱 2018-06-17
- bzoj1009 [ HNOI2008 ] -- KMP+矩阵乘法加速DP 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash