题目链接：https://www.luogu.org/problemnew/show/P3197
思路：首先考虑所有情况的个数，即每个位置都有$m$种可能，则方案数为$m^{n}$；接下来考虑不满足条件的情况，则一号位可以使用$m$种，二号位可以选择$m-1$种，三号位可以选择$m-1$种...$n$号位可以选择$m-1$种。
则最终可行的方案数为$m^{n}-m*(m-1)^{n-1}$。
注意模成负数的情况。
代码：
#include <bits/stdc++.h> const int p=100003; typedef long long ll; using namespace std; ll m,n; ll qpow(ll a,ll b){ ll ans=1; while(b){ if(b&1) ans=(ll)(ans*a)%p; a=(ll)(a*a)%p; b>>=1; } return ans%p; } int main(){ cin>>m>>n; cout<<((ll)qpow(m,n)%p-(ll)(m%p)*qpow(m-1,n-1)%p+p)%p<<endl; return 0; }
原文：https://www.cnblogs.com/BeyondLimits/p/11167028.html