奥数染色问题,染色木皮变色问题解决

描述
有一个圆形，分成n个扇形，用m种颜色给每个扇形染色，相邻扇形颜色不能相同。求方案总数。

不考虑对称性。
由于这个数可能很大，因此只需返回方案数模1e9 + 7。
1≤n≤105,1≤m≤105 1 ≤ n ≤ 10 5 , 1 ≤ m ≤ 10 5
​
样例
给定n = 2，m = 3，返回6。

解释：一个圆划分为 2 个扇形，用 3 种颜色上色方案有“黑红，黑白，白红，白黑，红白，红黑”6 种。

给定 n = 3，m = 2，返回 0。

解释：一个圆划分为 3 个扇形，用 2 种颜色上色，无论怎么上色，都没法保证相邻的颜色不同。

思路
dp[i]表示i个扇形m种配色的上色方案数，n个扇形的染色问题，可以转换为在n-1个扇形中插入一个扇形，有两种情况：
i）第1个扇形和第n-1个扇形的颜色不同，有dp[n-1] (由于两个扇形的颜色不同，上色方案是n-1个扇形m中配色)种情况，由于此扇形的颜色不能和另外两个相同，有m-2种颜色；
ii）第1个扇形和第n-1个扇形的颜色相同，有dp[n-2] (由于两个扇形的颜色相同，只需考虑n-2个扇形)种情况，由于此扇形的颜色不能和另外两个相同，有m-1种颜色
dp[n]=dp[n−1]∗(m−2)+dp[n−2]∗(m−1) d p [ n ] = d p [ n − 1 ] ∗ ( m − 2 ) + d p [ n − 2 ] ∗ ( m − 1 )
经过推倒最终结果可表示为
an=(m−1)n+(−1)n−2∗(m−1) a n = ( m − 1 ) n + ( − 1 ) n − 2 ∗ ( m − 1 )
可以使用动态规划，也可以直接求解

#ifndef C1444_H#define C1444_H#include<iostream>#include<vector>#include<cmath>using namespace std;class Solution {public: /** * @param n: the number of sectors * @param m: the number of colors * @return: The total number of plans. */ int getCount(int n, int m) { // Write your code here /* //动态规划求解 long long dp[100001]; long long num = 1e9 + 7; dp[1] = m; dp[2] = (long long)m*(m - 1) % num; dp[3] = (long long)m*(m - 1)*(m - 2) % num; for (int i = 4; i <= n; ++i) dp[i] = (dp[i - 1] * (m - 2) + dp[i - 2] * (m - 1))%num; return dp[n];*/ //直接求解得到结果 long long num = 1e9 + 7; long long res = myPow(m - 1, n) % num + pow(-1, n - 2)*(m - 1); return res; } //二分法求指数 long long myPow(int m, int n) { if (n == 0) return 1; if (n == 1) return m; long long num = 1e9 + 7; long long res = myPow(m, n >> 1); res = res * res % num; if (n & 1 == 1) res = res * m % num; return res; }};#endif