HDU 3923Invoker | 暑训Day1 C题填坑

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

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

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

附上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\n", t, ans);

	}

	return 0;

}

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

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

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