asp门户网站系统,学做网站看那个网,百度网站排名优化工具,个人网站建设好之后怎么赚钱1008: [HNOI2008]越狱 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 5166 Solved: 2242[Submit][Status][Discuss]Description 监狱有连续编号为1...N的N个房间#xff0c;每个房间关押一个犯人#xff0c;有M种宗教#xff0c;每个犯人可能信仰其中一种。如果相邻房间… 1008: [HNOI2008]越狱 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 5166 Solved: 2242[Submit][Status][Discuss] Description 监狱有连续编号为1...N的N个房间每个房间关押一个犯人有M种宗教每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同就可能发生越狱求有多少种状态可能发生越狱 Input 输入两个整数MN.1M10^8,1N10^12 Output 可能越狱的状态数模100003取余 Sample Input 2 3 Sample Output 6 HINT 6种状态为(000)(001)(011)(100)(110)(111) Source 题解终于捉了一道大水题 所有的可能宗教信仰方案为M^N 不可能越狱相邻两个房间的人的宗教信仰不同的方案为M*(M-1)^(N-1) 于是最终的答案 [M^N-M*(M-1)^(N-1)]%100003 1 #includeiostream2 #includecstdio3 #includecmath4 #includealgorithm5 #includequeue6 #includecstring7 #define PAU putchar( )8 #define ENT putchar(\n)9 using namespace std;
10 long long mod100003;
11 long long pow(long long x,long long y){
12 long long ans1;for(long long iy;i;i1,xx*x%mod)if(i1)ansans*x%mod;return ans%mod;
13 }
14 inline long long read(){
15 long long x0,sig1;char chgetchar();
16 while(!isdigit(ch)){if(ch-) sig-1;chgetchar();}
17 while(isdigit(ch)) x10*xch-0,chgetchar();
18 return x*sig;
19 }
20 inline void write(long long x){
21 if(x0){putchar(0);return;}if(x0) putchar(-),x-x;
22 int len0;long long buf[20];while(x) buf[len]x%10,x/10;
23 for(int ilen-1;i0;i--) putchar(buf[i]0);return;
24 }
25 long long n,m;
26 void init(){
27 mread();nread();
28 long long anspow(m,n);
29 ans(ansmod-m*pow(m-1,n-1)%mod)%mod;
30 write(ans);
31 return;
32 }
33 void work(){
34 return;
35 }
36 void print(){
37 return;
38 }
39 int main(){
40 init();work();print();return 0;
41 } 转载于:https://www.cnblogs.com/chxer/p/4640946.html
