Applese 涂颜色（组合数学 + 快速幂 + 费马小定理 + 大数运算）

客官°小女子只卖身不卖艺 2022-04-23 08:30 196阅读 0赞

链接：[https://ac.nowcoder.com/acm/contest/330/E][https_ac.nowcoder.com_acm_contest_330_E]  
来源：牛客网

精通程序设计的 Applese 叕写了一个游戏。

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

## 输入描述: ##

仅一行两个正整数 n, m，表示方阵的大小。

## 输出描述: ##

输出一个正整数，表示方案数对 109+7109+7 取模。

示例1

## 输入 ##

复制

1 1

## 输出 ##

复制

示例2

## 输入 ##

复制

2 2

## 输出 ##

复制

## 备注: ##

1≤n,m≤10100000

> 首先，通过运算可以得到 答案 ans =  2^n%mod （这里把mod定义为1e7）
> 
>  首先n的数字范围非常大，10的10万次方，所以数据一定是用字符串读进去的，C/C++选手头疼。
> 
> 使用Java写了半天头疼，用Python交一发过了。
> 
> 其次，因为 n 很大，循环n次肯定超时。
> 
> 这里用到费马小定理： ans = 2^n%mod = 2^( n%(mod-1) ) %mod.
> 
> 这样 n 就变成了 n%(mod-1) 了，但是mod 是1e7，直接循环还是太大了，
> 
> 这里就要用到快速幂取模算法。
> 
> 然后完美解决问题（人生苦短，请用Python）

def power(a,b,c):
        a=a%c
        ans=1
        while b!=0:
            if b&1:
                ans=(ans*a)%c
            b>>=1
            a=(a*a)%c
        return ans
    
    n,m = list(map(int,input().split()))
    mod = 1000000007
    ans = power(2,n%(mod-1),mod  )
    print(ans)
    
    exit(0)

> 觉得麻烦的人也可以这样写：
> 
> 答案就一行

print(pow(2,int(input().split()[0]),10**9+7))

[https_ac.nowcoder.com_acm_contest_330_E]: https://ac.nowcoder.com/acm/contest/330/E