牛客—开心的涂刷

题目链接：开心的涂刷

题意

有n个格子，m种颜色，需要找出存在两个相邻格子颜色相同的匹配数。

解题思路

要明白一共有多少种涂法，很明显就是$m^n$ ，那么只要找出所有的任意相邻颜色都不同的涂法就可以表示出存在两个相邻格子颜色相同的涂法。 那么任意相邻格子的颜色如何表达？很简单第一个格子可以选择任意一颜色，第二个格子要与前一个格子的颜色不相同那么只剩下（m-1）种颜色可以选择，以此类推，共有n * $(m-1{)}^{n-1}$种涂法。 然后可以用快速幂来计算$m^n$,$(m-1{)}^{n-1}$。 上代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1000000007; ll fastpow(ll a , ll n){ ll res = 1, base = a % mod;//这里一定要取mod因为m可能会大于mod while(n){ if(n & 1) res = (res * base) % mod; base = (base * base) % mod; n >>= 1; } return res; } int main(){ ll n, m, x, y, ans; cin >> n >> m; x = fastpow(m, n) % mod; y = (m % mod * fastpow(m - 1, n - 1)) % mod; if(x - y > 0)//因为取mod了，所以有可能x < y ，小于的话加一个mod就ok ans = (x - y) % mod; else ans = (x - y + mod) % mod; cout << ans << endl; return 0; }