HDU 3923 Invoker | 暑训Day1 C题填坑

暑训第一天，专题为组合数学与概率期望。

最近一个月都没有学习新的知识，上午听聚聚讲课头脑都是一片空白。加上长期没刷题，下午做练习题毫无感觉。到晚上总算理清了蓝书上的一些概念，跟着榜单做题。最后唯独剩下C题令人抓狂，照着蓝书代码敲上去一直WA，直到今天逐行对照网上博客修改才完全弄明白。

C题相当于蓝书P146的例题18项链与手镯，即求有m种颜色的n颗珠子组成的手镯的个数，也就是等价类的计数问题，直接使用Polya定理。

Input

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 )

Output

For each test case: output the case number as shown and then output the answer mod 1000000007 in a line. Look sample for more information.

Sample Input
2
3 4
1 2
Sample Output
Case #1: 21
Case #2: 1

附上AC代码：

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;
const int maxn = 10010;
const int mod = 1000000007;

int gcd(int a,int b)
{  // 最大公约数
    if(!b) return a;
    return gcd(b, a%b);
}

ll pow(ll a,ll n)
{  // 快速幂
    ll ans = 1;
    while(n)
    {
        if(n&1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

int main()
{

	int T, n, m;
	scanf("%d", &T);
	int t = 0;
	while(t++<T)
	{
		scanf("%d %d", &m, &n);  // m种颜色，n个珠子
		
		ll ans = 0;
                for(int i=0;i<n;i++)
		{  // 旋转的情况，循环数gcd(i,n)，其中i为顺时针旋转i格
                    ans += pow(m, gcd(i,n)) % mod;
                    ans %= mod; 
                }

		if(n&1)  //奇数的翻转情况，共n条对称轴，每条的循环数均为n/2+1
			ans += n * pow(m, n/2+1) % mod;
		else  //偶数的翻转情况，对称轴共n条，n/2条通过2个点，其余n/2条通过两点之间的中心
			ans += n/2 * (pow(m, n/2)+pow(m, n/2+1)) % mod;
		ans %= mod;
		ans = ans * pow(2*n, mod-2) % mod;  // 利用费马小定理，ans除以2n转化为ans乘上2n的逆元

		printf("Case #%d: %lld
", t, ans);
	}

	return 0;
}

自己手写实现gcd出了点状况，通过这题我才弄清楚了gcd(0,n) == n而gcd(1,n)==1.

关于求逆元的方法还有一种（扩展欧几里德），以后遇到了再总结吧。

Day 1的学习不算很顺利，还需要今后扩充相关数学知识以及疯狂刷题来加强。