Description

Input

Output

Sample Input

Sample Output

HINT

Source

正面考虑此题有点难，但从反面考虑就容易不少了，可以先求所有犯人互不冲突的方案数，第一个犯人有m种可能的宗教，为了不和第二个犯人冲突，第二个犯人有m-1种可能的宗教，第三个犯人也有m-1种可能的宗教。。。以此类推，方案数为m*[(m-1)^(n-1)]，所有犯人的搭配方案总数为m^n，则结果为m^n-m*[(m-1)^(n-1)]，由于题目数据范围太大，加之有输出mod后的结果的限制，用快速幂就OK

#include <stdio.h>#define MOD 100003#define LONG long long int//结果=m^n-m*[(m-1)^(n-1)]LONG pow(LONG x,LONG base) //快速幂,求(base^x)%MOD{	if(x==0) return 1;	LONG tmp=pow(x/2,base);	tmp*=tmp;	tmp%=MOD;	if(x&1) //x是奇数，则还要乘一次底数	{		tmp*=base;		tmp%=MOD;	}	return tmp;}int main(){	LONG n,m,compSet,uniSet,ans; //compSet=补集,uniSet=全集,ans=结果	scanf("%lld%lld",&m,&n);	compSet=pow(n-1,m-1);	uniSet=pow(n,m);	compSet*=m;	compSet%=MOD;	ans=uniSet-compSet;	if(ans<0) ans+=MOD; 	printf("%lld\n",ans);	return 0;}