题目大意

求\(m\)种数字组成的长度为\(n\)的序列的种数，序列中至少有一段连续的数字

分析

用可重排列的种数减去，相邻数字互不相同的序列种数

考虑相邻互不相同，第一个元素有\(m\)种可能，后面每个元素不能和它左边的那个数一样，有\(m-1\)种可能

即\[m^n - m(m-1)^{n-1}\]

代码

#include
    
     #include
     
      #include
      
       #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;}