链接:https://ac.nowcoder.com/acm/contest/330/E
来源:牛客网
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
精通程序设计的 Applese 叕写了一个游戏。
在这个游戏中,有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大,你需要将答案对 1e9+7 取模。
输入描述:
仅一行两个正整数 n, m,表示方阵的大小。
输出描述:
输出一个正整数,表示方案数对 1e9+7 取模。
示例1
输入
1 1
输出
2
示例2
输入
2 2
输出
4
备注:
1≤n,m≤10^100000
题意:不解释了吧,中文题~~~
下面用三种语言写一下~~
题解:因为每行最多两种情况,所以很容易看出是2^n%mod,因为n很大所以需要欧拉函数降幂,用到公式 2^n%mod=2^(n%get_euler(mod))%mod,这样进行降幂,上代码:
注意:其实质数的欧拉值就是本身减1!!
C++:我还是写了一下欧拉函数~~~~
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll get_euler(ll n){ // 欧拉函数模板
ll res=n,a=n;
for (ll i = 2; i*i<=a;i++){
if(a%i==0){
res=res/i*(i-1);
while(a%i==0) a=a/i;
}
}
if(a>1) res=res/a*(a-1);
return res;
}
ll mul(ll a,ll b,ll c)//骚快速幂模板
{
ll ans=0;
while(b)
{
if(b&1)
{
ans=(ans+a)%c;
}
a=(a<<1)%c;
b>>=1;
}
return ans;
}
ll quick(ll a,ll b,ll c) //骚快速幂模板
{
ll ans=1;
a=a%c;
while(b!=0)
{
if(b&1) ans=mul(ans,a,c);
b>>=1;
a=mul(a,a,c);
}
return ans;
}
int main(){
string s,m;
cin >> s >> m;
ll p=get_euler(mod);
ll sum=0;
for (int i = 0; i < s.size();i++){
sum=(sum*10+s[i]-'0')%p;//降幂,可以这样写,不影响结果~这是取模运算,记住吧!
}
cout << quick(2,sum,mod) << endl;
return 0;
}
java: 用的大数,也需要降幂,不降幂超时~
import java.util.*;
import java.math.*;
public class Main{
static Scanner cin = new Scanner(System.in);
static BigInteger x = new BigInteger("2");
static BigInteger w = new BigInteger("1000000007");
static BigInteger ww = new BigInteger("1000000006");
static BigInteger quick(BigInteger a,BigInteger b) {//快速幂
BigInteger ans = BigInteger.ONE;
while(b.compareTo(BigInteger.ZERO)!=0) {
if(b.mod(x).intValue()==1) {
ans = ans.multiply(a).mod(w);//虽然是大数,这里也要mod,不然会超时的,因为数太大了,运算会麻烦的~~
}
b=b.divide(x);
a=a.multiply(a).mod(w);
}
return ans.mod(w);
}
public static void main(String[] args) {
BigInteger n,m;
n=cin.nextBigInteger();m=cin.nextBigInteger();
n=n.mod(ww);//记住要降幂,不降幂超时
BigInteger sum=quick(x,n);
System.out.println(sum);
}
}
Python3:
看大佬用Python3写的这个题,太简单了~~自学一下~~不用降幂啥的,直接搞!!上代码:
print(pow(2,int(input().split()[0]),10**9+7))
一行代码解决一切~~~既然现在还不会这门语言,就先暂且记住! 马上去学~~~