暑假集训-组合数学及数论

群——Burnside定理

容斥原理

A题

　　组合数学。

　　f[i] = (f[i - 1] * c[sum[i] - 1][a[i] - 1])

　　群，置换，Burnside定理，还不懂。

　　n个数中求与自己互质的个数，分解质因子后容斥原理。

　　枚举a出现的次数，满足条件后求这种数的个数，乘法逆元。

　　用map将距离映射到对应的代价，将能够到达的距离存在vector中并标记，不断用原数列中的数与vector中的数求gcd，并更新gcd的代价。输出map[1]

　　最简单的中国剩余定理

　　数位DP，先预处理出f[i][j]表示i位长的二进制数中含有j个1的个数有多少，这实际上就是C(i,j)。

　　对每一个n，二进制长度为m。从1到m求出有这么多1的个数是多少，用快速幂求结果，再和原来的数乘起来。

　　数学题。

　　分解质因子后各指数分别是a1,a2...an。对于不同的数对，只要指数不同，最后的数就会不同。对于ai,可以产生2*ai+1个数对。