Welcome to my blog. The English verison of posts are in En page.
项链和手镯。
项链的问题在于不可以翻转，因此少了一种置换，而手镯则可以反转。然后我们计算旋转的置换。
旋转的步长可以是0,i,2i…然后我们可以得出循环一共有n/gcd(i,n)个元素，因此，我们可以计算出一共有gcd(i,n)个循环。则不定点的个数为
$a = \Sigma t^{gcd(i,n)}$。
翻转。翻转奇数情况和偶数情况是不一样的，因为奇数情况会多一个不定点，这个不定点就是在轴上的点。剩余的不定点的个数就是$n/2$，总共不定点的个数就是$nt^{(n+1)/2}$。偶数的情况下，如果正好切在两个珠子上，那么循环长度为2的点有$n/2-1$个，长度为1的循环有2个，所以总共$n/2+1$个。如果没有切在珠子上，不定点的个数为$n/2$，和为$b = n/2*(t^{n/2+1} + t^{n/2})$。
然后我们可以计算出项链的个数$a/n$，手镯的个数$(a+b)/2n$
列出式子以后代码就方便了。记得求pow的时候可以顺手打表
终于搞明白置换了，可喜可贺。建议不要看屈的离散数学，看白书即可，通俗易懂。
我在这里简单阐述一下，当然也是依据李大大的书。
置换就是把n个元素全排列，置换可以定义乘法。
循环就是置换的移位。例如：
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 3 | 5 | 1 | 4 | 2 |
即为(1 3)(2 5)(4)
其中，(1 3)通过这个置换发现形成一个循环，(2 5)通过这个置换形成一个循环，(4)本身构成一个循环。
对于一个置换f，若一个着色方案s经过置换后不变，则称s为f的不动点，将f的不动点记录为C(f)，则可证明等价类数目为所有C(f)的平均值，成为Burnside引理。
一般的，如果f分解成m(f)个循环的乘积，那么每个循环的所有格子的颜色必须相同。（因为这样才是一个不动点）。
假设涂k种颜色，则有
$$C(f) = k^{m(f)}$$
（乘法原理。循环内相同，循环间可以不同）。
代入Burnside引理之后得到Polya定理：等价类的个数等于所有置换f的$k^{m(f)}$的平均数。
本题目计算开根号数字，给出Y求X。X = sqrt(Y)，主要问题在Y的超大数据。
时间限制是3s。我使用的大数模板中没有一个大数除大数的算法，因此直接借用Java来搞一搞。
利用公式$$(5/x+x)/2 = x$$递归逼近求解。这个公式比较好推，移项即可。
参考他人代码，不需要用set，直接判断是否和前一个相等即可= =。
再一个就是模拟手算。手算法有些麻烦。。注意第二个除数开始余数*20即可。
基本上是组合数裸题。。
给出$(x_1+x_2+x_3….x_k)^n$，要求计算$x_1^{n_1}x_2^{n_2}…x_k^{n_k}$的系数。
思想就是从一个算式中取出$n_k$，即$C_n^{n_k}$，然后减去$n_k$，如果直接相乘则会重复。
比较莫名奇妙的题目，明明是搜索题目居然放在了数学分类，完全找不到数学的影子。。
利用vector，遍历树，找出最大的子树路径，然后与次大的子树路径相加即为答案。
因为图表示这方面太渣，基本上抄袭了别人的代码= =
有些匪夷所思的题目。。注释部分加上就WA，不加就AC。。
推公式，因为$$C(n,k) = C(n,k-1) * (n-k+1)/k$$
所以$$ans = \frac{C(n, k)}{C(r, s)}\qquad$$改成递推即可。
后面的三位快速幂即可，但是前面三位不好求。经过分析，每一位都有可能牵扯到前三位的值，因此无法具体的作出判断。
如果使用模方法省去后面的部分，必定会造成误差，随着省略的部分增多，误差积累势必会越来越大。（错了一组数据）
最佳的方法还是数学分析（参考了题解）：
分析n，$a = log_{10}^n$，则$n = a ^ {10}$。分解a = i + d，i为正数部分，d为小数部分。那么i影响的仅仅是位数，d影响的则是具体的数字。
这样得到的值是准确的。另外对浮点数取余
给出一个Answer(x,y)函数，x,y属于[1,N]，$Answer(k_x, k_y)$可以由Answer(x,y)得出，目的是求需要计算多少Answer(x,y)。
就是求1,N范围的欧拉函数的加和。欧拉函数的定义是与N互质的数的个数，所以需要如此计算。一开始没有发现就是求欧拉惭愧惭愧。
一开始在扩展gcd上想了许久没有办法将得出的数字直接转换成为相应的输出，后来发现就是模方程。
因为不求最佳解，所以直接使用ca*x = n (mod cb)即可。这个方程的解可以覆盖全部的n，因为该方程如果有解，则n是gcd(ca, cb)的倍数。因为ca, cb互质 gcd (ca, cb) = 1，所以明显通过单纯的加满B，向A中倒，然后清空A就可以遍历所有n的解（尽管可能不是最佳解）。
不能是cb*x = n (mod ca)，因为n可能大于ca.
如果求最佳解，显然是bfs。当然这到题目也可以dfs来做，不过明显要复杂很多。
今天不适合刷题。。。
题意：一个桌子4条腿，每条腿由一种硬币构成，四条腿必须一样长，请问如何最接近给出的标准桌子高度，输出两个最接近的值。
更新两个值的时候错误的判断如果lcm大于h就不再更新了，却没有想到高于h的部分依然可以更新，只是不能更新小于h的部分了。