HDU 3923 Ploya定理

来源：http://acm.hdu.edu.cn/showproblem.php?pid=3923

题意：有m种元素，要围成长度为n的圈，问有多少种方法。

思路：可以转化成有m种颜色，要围成长度为n的项链，有多少种方法。裸的Ploya定理，但是最后除的地方用到了乘法逆元。这是今天新的收获，学习了。

因为我们得到的sum值是一直不断的模Mod的结果，所以最后我们不能直接用sum/2*n % Mod来计算结果，因为此时的sum是模后的值，并不是真正的sum。这时我们需要算出2*n在Mod中的乘法逆元为x，则sum * x % Mod即为答案。

代码：

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;

#define Mod 1000000007
__int64 gcd(__int64 a,__int64 b){
	if(b == 0)
		return a;
	return gcd(b,a%b);
}
__int64 mi(int x,int n){
	__int64 s = 1;
	for(__int64 i = 1;i <= n;++i)
		s = ((s%Mod) * (x%Mod))%Mod;
	return s;
}
void extend_Eulid(__int64 a,__int64 b,__int64 &x,__int64 &y){
	if(b == 0){
	  x = 1;
	  y = 0;
	  return;
	}
	extend_Eulid(b,a%b,x,y);
	__int64 temp = x;
	x = y;
	y = temp - a/b * y;
}
int main(){
	//freopen("1.txt","r",stdin);
	//freopen("2.txt","w",stdout);
	__int64 numcase;
	scanf("%I64d",&numcase);
	for(__int64 k = 1;k <= numcase;++k){
	  __int64 color,len;
	  scanf("%I64d%I64d",&color,&len);
	  __int64 sum = 0;
	  for(__int64 i = 1;i <= len;++i){
	    __int64 x = gcd(len,i);
		sum += mi(color,x);
	  }
	  if(len % 2 == 0)
		  sum += ((len/2 * mi(color,len/2))%Mod + (len/2 * mi(color,len/2+1)) % Mod) % Mod;
	  else
		  sum += (len * mi (color,(len-1)/2+1)) % Mod;
	  __int64 xx,yy;
	  extend_Eulid(2*len,Mod,xx,yy);
	  xx = (xx % Mod + Mod) % Mod;
	  printf("Case #%I64d: %I64d\n",k,(sum%Mod * (xx%Mod)) % Mod);
	}
	return 0;
}