链接:https://ac.nowcoder.com/acm/contest/330/E
来源:牛客网
题目描述
精通程序设计的 Applese 叕写了一个游戏。
在这个游戏中,有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大,你需要将答案对 109+7109+7 取模。
输入描述:
仅一行两个正整数 n, m,表示方阵的大小。
输出描述:
输出一个正整数,表示方案数对 109+7109+7 取模。
备注:
1≤n,m≤10100000
欧拉降幂加快速幂解决
这些不会的自学百度吧。。或者CSDN上也有很多大佬的解释
对于这个题一个比较显然的结论是,对于每一行有2种涂色方法。
因为只是要左右不同所以前一行不影响后一行因此答案就是 2^n 。
ac代码(c++)
#include <stdio.h> #include<string.h> typedef long long ll; char a[1000006]; ll x,z; ll quickpow(ll x,ll y,ll z) { ll ans=1; while(y) { if(y&1) ans=ans*x%z; x=x*x%z; y>>=1; } return ans; } ll phi(ll n) { ll i,rea=n; for(i=2;i*i<=n;i++) { if(n%i==0) { rea=rea-rea/i; while(n%i==0) n/=i; } } if(n>1) rea=rea-rea/n; return rea; } int main() { while(scanf("%lld %s %lld",&x,a,&z)!=EOF) { ll len=strlen(a); ll p=phi(z); ll ans=0; for(ll i=0;i<len;i++) ans=(ans*10+a[i]-‘0‘)%p; ans+=p; printf("%lld\n",quickpow(x,ans,z)); } return 0; }
然后是py的。。py对于大数处理真滴太方便了。呜呜呜,哭了
print(pow(2, int(input().split()[0]), 10**9 + 7))
、