题目大意
已知序列$P$满足$|P|=N$，（以下所有$i,i\in[1,N]$）$\forall i, P_i\in [1,M]$。求$|\{P|\exists i, P_i =P_{i+1}\}|$。
题解
容易想到运用正难则反的思想，先求出所有情况种数，再求出不符合情况种数。
但这里“所有”是什么？是全排列吗？又是什么的全排列呢？“不符合”又是什么呢？我们说不清楚。
那么怎么想？直接整体考虑太难，我们应当一位一位考虑。$\forall i,P_i$有$M$种取值。因此所有情况种数为$M^N$。关于不符合情况种数，第一位情况有$M$个，以后每一位为了不与前面相等，情况数为$M-1$。由乘法原理，不符合情况为$M(M-1)^{N-1}$。故答案为：$M^N-M(M-1)^{N-1}$。
注意
$(a-b)\mod p\neq a\mod p-b\mod p$，$(a-b)\mod p=(a\mod p-b\mod p+p)\mod p$。
#include <cstdio>
#include <cstring>
using namespace std; #define ll long long ll Mult(ll a, ll b, ll p)
{
ll ans = 0;
while (b)
{
if (1 & b)
ans = (ans + a) % p;
a = (a + a) % p;
b >>= 1;
}
return ans;
} ll Power(ll a, ll n, ll p)
{
ll ans = 1;
while (n)
{
if (n & 1)
ans = Mult(ans, a, p);
a = Mult(a, a, p);
n >>= 1;
}
return ans;
} int main()
{
const ll P = 100003;
ll n, m;
scanf("%lld%lld", &m, &n);
printf("%lld\n", (Power(m, n, P) - Mult(m, Power(m - 1, n - 1, P), P) + P) % P);
return 0;
}