题解 | #开心的涂刷#

考察知识点：数学、快速幂

$nn$ 个格子处于同一排，忽略限制最多有 $m^{n}m^n$ 种涂法。

考虑让小明不开心的涂法，易知这样的涂法有 $m(m-1{)}^{n-1}m(m-1)^\{n-1\}$ 种，因为第一个格子可以从 $mm$ 种颜色中任选，后面的格子只能从与上一个格子不同的 $m-1m-1$ 种颜色中任选。

最终答案即为 $m^n-m(m-1{)}^{n-1}m^n-m(m-1)^\{n-1\}$，用快速幂优化即可。

时间复杂度：$O(\log n)O(\backslash log\; n)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define MOD 1000000007

ll qpw(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void solve()
{
    ll n, m;
    cin >> n >> m;
    m %= MOD;
    ll ans = (qpw(m, n) - m * qpw(m - 1, n - 1) % MOD + MOD) % MOD;
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}