[关键字]：数学
[题目大意]：监狱里有n个犯人信奉m种宗教，问有两个信奉相同宗教的犯人埃在一起的方案数。
//=============================================================================
[分析]：如果想到反向思维你就成功了！所有方案数=mn没有两个宗教相同的犯人挨在一起的方案数是m*(m-1)*(m-1)……*(m-1)=(m-1)n-1,所以答案就是mn-(m-1)n-1
[代码]：
View Code #include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>using namespace std;const int MOD=100003;long long n,m,x,ans,ans2;long long Work(long long n){if (n==1) return x%MOD;if (n==0) return 1%MOD;long long temp=Work(n/2);//printf("%I64d\n",temp); temp=(temp*temp)%MOD;if (n%2==1) temp=(temp*x)%MOD;return temp;}int main(){ freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); scanf("%I64d%I64d",&m,&n); x=m; ans=Work(n); x=m-1; ans2=Work(n-1); ans2=(ans2*m)%MOD; printf("%I64d\n",(ans+MOD-ans2)%MOD);//system("pause"); return 0;}转载于:https://www.cnblogs.com/procedure2012/archive/2012/04/06/2435504.html
相关资源：垃圾分类数据集及代码