开心的涂刷

链接：https://ac.nowcoder.com/acm/problem/14718
来源：牛客网

题目描述

一天小明同学拿着m种颜色的油漆去涂刷n块格子，在涂刷的过程中他发现有很多种涂色方案，并很快的算出了答案，然后他发现如果涂好颜色的格子中只要存在某两个相邻的格子颜色一样，他就会感到开心，他想知道有多少种让他开心的涂刷方案。

输入描述:

输入仅包含一行，包含两个数n，m分别表示格子数和颜色数。（1 <= n <= 1e12, 1 <= m <= 1e12)

输出描述:

输出一行包含一个整数，让小明开心的涂刷方案数。 答案对1000000007取模

示例1

输入

复制

3 2

输出

复制

说明

一共有(1, 1, 2), (2, 1, 1), (2, 2, 1), (1, 2, 2), (1, 1, 1), (2, 2, 2) 这6种方案


一共有mⁿ种涂法，那么不相邻的涂法是，第一个有m种，那么剩下的每一个都有m-1种。不相邻总共m*(m-1)^(n-1)种。用总数减去不相邻数这个就行。
代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll fastpow(ll a,ll b)
{
    ll ans=1;
    a=a%mod;
    while(b)
    {
        if(b&1)
            ans=a*ans%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll n,m;
    cin>>n>>m;
    m=m%mod;
    ll ans=fastpow(m,n)%mod-m*fastpow(m-1,n-1)%mod;
    cout<<(ans+mod)%mod;
    return 0;
}

有一个性质：（a*b）%mod = （a%mod）*（b%mod）%mod，这个性质在a和b是大数的时候用的

快速幂中，求a^b%mod，有的编译器，计算5%3=2；有的算出来5%3=-1

为了避免这种误差，统一用：ans=（ans+mod）%mod

就可以把这个都化成正的最小的那个数了。