题目大意
求\(m\)种数字组成的长度为\(n\)的序列的种数，序列中至少有一段连续的数字
分析
用可重排列的种数减去，相邻数字互不相同的序列种数
考虑相邻互不相同，第一个元素有\(m\)种可能，后面每个元素不能和它左边的那个数一样，有\(m-1\)种可能
即$$m^n - m(m-1)^{n-1}$$
代码
#include<iostream>
#include<cmath>
#include<cstdio>
#define LL long long
using namespace std;
const LL p = 100003;
LL pw(LL a,LL b){
LL t = 1;
for (;b;b >>= 1) {
if (b & 1) t = t * a % p;
a = a % p * a % p;
}
return t;
}
int main(){
LL n,m;
scanf("%lld%lld",&m,&n);
printf("%lld\n",(p + pw(m,n) - m * pw(m - 1,n - 1) % p) % p);
return 0;
}
