暑训第一天，专题为组合数学与概率期望。
最近一个月都没有学习新的知识，上午听聚聚讲课头脑都是一片空白。加上长期没刷题，下午做练习题毫无感觉。到晚上总算理清了蓝书上的一些概念，跟着榜单做题。最后唯独剩下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 2Sample 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\n", t, ans);
} return 0;
}
自己手写实现gcd出了点状况，通过这题我才弄清楚了gcd(0,n) == n而gcd(1,n)==1.
关于求逆元的方法还有一种（扩展欧几里德），以后遇到了再总结吧。
Day 1的学习不算很顺利，还需要今后扩充相关数学知识以及疯狂刷题来加强。