Description

Solution

正向考虑需要去重，反向考虑：如果每个相邻的人宗教都不同，对于第一个位置有\(m\)种选择，第二个位置有\(m-1\)个选择，第三个位置也有\(m-1\)个选择......由此可知方案数为\(m\cdot (m-1)^{n-1}\)。又有总方案数为\(m^n\)，所以所求方案数为\(m^n-m\cdot (m-1)^{n-1}\)。

小优化：快速幂可以用费马小定理加速（44ms->8ms）

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        typedef long long LL;const LL MOD = 100003;LL n, m; inline LL pow_mod(LL x, LL p, LL mod) {    x %= mod;     p %= mod-1; // 费马小定理    LL ans = 1;    for (; p; p >>= 1) {        if (p & 1) ans = ans * x % mod;        x = x * x % mod;     }    return ans;}int main() {    std::cin >> m >> n;    std::cout << (pow_mod(m, n, MOD) - m % MOD * pow_mod(m-1, n-1, MOD) % MOD + MOD) % MOD;    return 0;}