首页 > ACM题库 > HDU-杭电 > HDU 3923-Invoker-组合数学-[解题报告]HOJ
2015
04-14

HDU 3923-Invoker-组合数学-[解题报告]HOJ

Invoker

问题描述 :

On of Vance’s favourite hero is Invoker, Kael. As many people knows Kael can control the elements and combine them to invoke a powerful skill. Vance like Kael very much so he changes the map to make Kael more powerful.

In his new map, Kael can control n kind of elements and he can put m elements equal-spacedly on a magic ring and combine them to invoke a new skill. But if a arrangement can change into another by rotate the magic ring or reverse the ring along the axis, they will invoke the same skill. Now give you n and m how many different skill can Kael invoke? As the number maybe too large, just output the answer mod 1000000007.

输入:

The first line contains a single positive integer T( T <= 500 ), indicates the number of test cases.
For each test case: give you two positive integers n and m. ( 1 <= n, m <= 10000 )

输出:

The first line contains a single positive integer T( T <= 500 ), indicates the number of test cases.
For each test case: give you two positive integers n and m. ( 1 <= n, m <= 10000 )

样例输入:

2
3 4
1 2

样例输出:

Case #1: 21
Case #2: 1

Hint
For Case #1: we assume a,b,c are the 3 kinds of elements. Here are the 21 different arrangements to invoke the skills / aaaa / aaab / aaac / aabb / aabc / aacc / abab / / abac / abbb / abbc / abcb / abcc / acac / acbc / / accc / bbbb / bbbc / bbcc / bcbc / bccc / cccc /

来源: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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/wmn_wmn/article/details/7821690


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢