首页 > 其他 > 详细

bzoj 1008: [HNOI2008]越狱

时间:2015-04-28 20:50:36      阅读:227      评论:0      收藏:0      [点我收藏+]

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1008

简单容斥:

总状态数 A=M^N

不越狱的状态数 B=M*(M-1)^(N-1)

越狱的状态数 ans=A-B

技术分享
 1 /*
 2  * Problem: BZOJ 1008 
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/4/28 星期二 16:29:02
 5  * File Name: 233.cpp
 6  * State: Accepted
 7  * Memo: 容斥
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 typedef long long int64;
17 
18 const int MOD=1e5+3;
19 
20 int64 M, N;
21 int64 pow(int64 a, int64 n, int64 mod) {
22     int64 res=1;
23     while(n) {
24         if(n&1) res=(res*a)%mod;
25         a=(a*a)%mod;
26         n>>=1;
27     }
28     return res;
29 }
30 int main() {
31 #ifndef ONLINE_JUDGE
32     freopen("in", "r", stdin);
33     //freopen("out", "w", stdout);
34 #endif
35     while(~scanf("%lld%lld", &M, &N)) {
36         int64 ans=M*(pow(M, N-1, MOD)-pow(M-1, N-1, MOD))%MOD;
37         printf("%lld\n", (ans+MOD)%MOD);
38     }
39     return 0;
40 }
bzoj 1008

 

bzoj 1008: [HNOI2008]越狱

原文:http://www.cnblogs.com/shjwudp/p/4463740.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!