Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 8681 Solved: 3746
监狱有连续编号为1...N的N个房间,每个房间关押一个犯人,有M种宗教,每个犯人可能信仰其中一种。如果 相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱
输入两个整数M,N.1<=M<=10^8,1<=N<=10^12
可能越狱的状态数,模100003取余
2 3
6
6种状态为(000)(001)(011)(100)(110)(111)
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1008
分析:快速幂取模运算,暂时先不解释,日后解释!
下面给出AC代码:
1 #include <bits/stdc++.h>
2 const int mod =100003;
3 using namespace std;
4 long long n,m;
5 inline long long pow(long long a,long long b)
6 {
7 long long res=1;
8 while(b)
9 {
10 if(b&1) res=(res*a)%mod;
11 a=(a*a)%mod;
12 b>>=1;
13 }
14 return res;
15 }
16 int main()
17 {
18 cin>>m>>n;
19 long long a=pow(m,n);
20 long long b=(pow(m-1,n-1)*(m%mod))%mod;
21 a+=mod;
22 cout<<(a-b)%mod<<endl;
23 return 0;
24 }
更为简便的写法【之后补题的】
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int mod=100003;
4 typedef long long ll;
5 inline ll read()
6 {
7 ll x=0,f=1;
8 char ch=getchar();
9 while(ch<'0'||ch>'9')
10 {
11 if(ch=='-')
12 f=-1;
13 ch=getchar();
14 }
15 while(ch>='0'&&ch<='9')
16 {
17 x=x*10+ch-'0';
18 ch=getchar();
19 }
20 return x*f;
21 }
22 inline ll qpow(ll x,ll p)
23 {
24 ll ret=1;
25 for(;p;p>>=1,x=x*x%mod)
26 {
27 if(p&1)
28 ret=ret*x%mod;
29 }
30 return ret;
31 }
32 ll m,n;
33 int main()
34 {
35 m=read();
36 n=read();
37 ll a=qpow(m,n);
38 ll b=b=((m%mod)*qpow(m-1,n-1))%mod;
39 ll ans=(a+mod-b)%mod;
40 cout<<ans<<endl;
41 return 0;
42 }