Applese 涂颜色(欧拉降幂)

传送门 牛客训练赛4E

描述

精通程序设计的 Applese 叕写了一个游戏。
在这个游戏中,有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大,你需要将答案对 1e9+7 取模。

输入

仅一行两个正整数 n, m,表示方阵的大小。(1<=n,m<=10^100000)

输出

输出一个正整数,表示方案数对 1e9+7取模。

样例

  • Input
    1 1
    2 2
  • Output
    2
    4

思路

  • 显然答案是(2^n)%mod,但是n太大,需要欧拉降幂,也就是n=n%phi(mod)+phi(mod),然后快速幂;
  • n采用字符串读入,按位模
    1
    2
    for(LL i=0;i<len;i++)
    sum=(sum*10+n[i]-'0')%p;

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
#define INIT(a,b) memset(a,b,sizeof(a))
#define LL long long
using namespace std;
const int MAX=0x7fffffff;
const int MIN=-0x7fffffff;
const int INF=0x3f3f3f3f;
const double pi=acos(-1);
const int mod=1e9+7;
LL qpow(LL x,LL n){
LL ans=1;
while(n>0){
if(n&1)ans=(ans*x)%mod;
x=(x*x)%mod;
n/=2;
}
return ans;
}
int main(){
string n,m;
cin>>n>>m;
LL p=mod-1,len=n.size(); //mod是素数 phi(mod)=mod-1
LL sum=0;
for(LL i=0;i<len;i++)
sum=(sum*10+n[i]-'0')%p;
sum+=p;
cout<<qpow(2,sum)<<endl;
return 0;
}
Donate comment here