开心的涂刷

NC14718. 开心的涂刷

描述

一天小明同学拿着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种方案

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 5ms, 内存消耗: 504K, 提交时间: 2021-04-19 21:40:54

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

Python3 解法, 执行用时: 42ms, 内存消耗: 4528K, 提交时间: 2022-12-10 20:22:32

a,b=map(int,input().split());c=1000000007
print((pow(b,a,c)-b*pow(b-1,a-1,c)+c)%c)