1008: [HNOI2008]越獄
Time Limit:?1 Sec??Memory Limit:?162 MBSubmit:?5166??Solved:?2242
[Submit][Status][Discuss]
Description
監獄有連續編號為1...N的N個房間，每個房間關押一個犯人，有M種宗教，每個犯人可能信仰其中一種。如果相鄰房間的犯人的宗教相同，就可能發生越獄，求有多少種狀態可能發生越獄
Input
輸入兩個整數M，N.1<=M<=10^8,1<=N<=10^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 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #define PAU putchar(' ') 8 #define ENT putchar('\n') 9 using namespace std; 10 long long mod=100003; 11 long long pow(long long x,long long y){ 12 long long ans=1;for(long long i=y;i;i>>=1,x=x*x%mod)if(i&1)ans=ans*x%mod;return ans%mod; 13 } 14 inline long long read(){ 15 long long x=0,sig=1;char ch=getchar(); 16 while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();} 17 while(isdigit(ch)) x=10*x+ch-'0',ch=getchar(); 18 return x*=sig; 19 } 20 inline void write(long long x){ 21 if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x; 22 int len=0;long long buf[20];while(x) buf[len++]=x%10,x/=10; 23 for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return; 24 } 25 long long n,m; 26 void init(){ 27 m=read();n=read(); 28 long long ans=pow(m,n); 29 ans=(ans+mod-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 }
?
)
