思路：
总共有m^n次方种方案，其中相邻两个都不相同的有m * (m - 1) ^ (n - 1)种，两者相减就是答案
代码：
#include<bits/stdc++.h> using namespace std; #define LL long long #define pb push_back #define mem(a, b) memset(a, b, sizeof(a)) const int mod = 1e5 + 3; LL q_pow(LL n, LL k) { LL ans = 1; while (k) { if (k & 1) ans = (ans * n) % mod; n = (n * n) % mod; k >>= 1; } return ans; } int main() { LL m, n; scanf("%lld%lld", &m, &n); LL tot = q_pow(m % mod, n); LL tmp = (m % mod)*q_pow((m - 1) % mod, n - 1); tot = ((tot - tmp) % mod + mod) % mod; printf("%lld\n", tot); return 0; }