2015
04-14

# 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

HintFor 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 / 

因为我们得到的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;
}


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