【BZOJ1008】[HNOI2008]越狱

题目链接

(solution)

用总方案数减去不发生越狱的方案数就行了

#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;

const int MOD=100003;

int n,m;

inline int qpow(int x,int k){
	int s=1;
	while(k){
		if(k&1) s=s*x%MOD;
		k>>=1;
		x=x*x%MOD;
	}
	return s;
}

signed main()
{
	scanf("%lld%lld",&m,&n);
	m%=MOD;
	printf("%lld
",(qpow(m,n)-m*qpow(m-1,n-1)%MOD+MOD)%MOD);
	return 0;
}