「CODEVS1851」越狱
题目描述 Description
监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
输入描述 Input Description
输入两个整数M，N.1<=M<=10^8,1<=N<=10^12
输出描述 Output Description
可能越狱的状态数，模100003取余
样例输入 Sample Input
2 3
样例输出 Sample Output
6
数据范围及提示 Data Size & Hint
6种状态为(000)(001)(011)(100)(110)(111)
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <cstdio> #include <iostream> const long long d=100003; long long n,m; int pow(long long p,long long k) { long long temp=1,c=p; while(k) { if(k&1)temp=(temp*c)%d; c=(c*c)%d; k=k>>1; } return temp; } int main() { scanf("%lld%lld",&m,&n); long long temp1=(pow(m-1,n-1)*m)%d; long long temp2=pow(m,n); printf("%lld\n",(temp2-temp1+d)%d); return 0; } |
Subscribe
计数器 9786454
OI 课件=>
OI 课件=>