本题要是没有点数学知识还真不太好做。首先我们想相邻的有都少种，但是这样想很明显太复杂了，可以想反面，如果算出不相邻的，用总数减去不相邻的就可以了。
总数由乘法原理可知是mn，（乘法原理，第一个位置有m种选择，第二个位置也是m种，依次类推，总共m*m*......m种，有几个位置就乘以几个m），
那题目的反面就是第一个位置有m种可能，第二个位置要和它不一样就有m-1种可能，第三个位置要和第二个位置不一样又有m-1种可能，这样题目反面（没相邻一样）的个数就是m*((m-1)(n-1))种。
用总数减去题目反面即可。
注意本题有可能最后为负数，要保证是正数。数据较大，用快速幂。
代码如下：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 typedef long long ll; 5 const int mod=100003; 6 ll fpow(ll x,ll y)//快速幂 7 { 8 ll res=1; 9 while(y) 10 { 11 if(y&1) 12 { 13 res=res*x%mod; 14 } 15 x=x*x%mod; 16 y>>=1; 17 } 18 return res%mod; 19 } 20 int main() 21 { 22 ll n,m; 23 cin>>m>>n; 24 ll ans; 25 ans=(fpow(m,n)-m*fpow((m-1),(n-1)))%mod; 26 if(ans<0)//可能为负 27 { 28 ans+=mod; 29 ans%=mod; 30 } 31 cout<<ans; 32 return 0; 33 }
原文：https://www.cnblogs.com/theshorekind/p/12718504.html