zhongzihao/projecteuler

152. Writing 1/2 as a sum of inverse squares

题目大意：问有多少种方式将 \(\frac{1}{2}\) 表示成 \(2\sim80\) 之间的不同数的倒数平方和。

题解：感觉除了暴力没啥好的性质。首先将所有倒数平方乘上 \(\text{lcm}(2^{2},\cdots,80^{2})\)，就转成了一个 meet-in-middle 问题。但是将近 \(80\) 个数太多了。不知道为什么就发现了有很多数是不可能选取的。具体来说，选取 \(\text{lcm}\) 的一个小约数，你会发现大部分的元素模它为 \(0\)，对于模它不为 \(0\) 的所有元素，直接 \(2^{n}\) 枚举一下组合，然后就会发现有些数永远不能出现在组合中，否则就没法凑出 \(0\)。随便选一些（其实是有一些规律的）约数筛完后，就只剩下 \(30\) 多个可选的元素了。

443. GCD sequence

题目大意：设 \(f(4)=13,f(n)=f(n-1)+\gcd(n,f(n-1))(n\ge5)\)，求 \(f(10^{15})\)。

题解：可以猜测会有大段连续的 \(1\)。如果 \(\gcd(n,f(n-1))=1\)，那么下一个合法的位置应该和 \(f(n-1)-n\) 不互质，随便算算就好。实际只需要迭代几百次（很可能中间有一个大质数）。

479. Roots on the Rise

题目大意：设 \(a_{k},b_{k},c_{k}\) 是方程 \(\frac{1}{x}=(\frac{k}{x})(k+x^{2})-kx\) 的三根，求 \(\sum_{k=1}^{10^{6}}\sum_{p=1}^{10^{6}}(a_{k}+b_{k})^{p}(b_{k}+c_{k})^{p}(c_{k}+a_{k})^{p}\)。

题解：方程化简为 \(x^{3}-kx^{2}+\frac{1}{k}x-k^{2}=0\)。注意到 \((a_{k}+b_{k})(b_{k}+c_{k})(c_{k}+a_{k})=(a_{k}+b_{k}+c_{k})(a_{k}b_{k}+b_{k}c_{k}+c_{k}a_{k})-a_{k}b_{k}c_{k}=1-k^{2}\)，等比数列求和一下就好了。似乎很多情况下轮换对称式都能用根与系数的关系来表示呢。

488. Unbalanced Nim

题目大意：给你三堆石子，每堆石子的数量互不相同，两人轮流取走石子，每次可以选择一堆，从中取走一个以上的石子，要求取完之后仍要满足每堆石子的数量互不相同，最后不能操作者输。设三堆石子的数量分别为 \(a,b,c\)，设 \(F(n)\) 表示满足 \(0<a<b<c<n\) 的所有负态的 \((a+b+c)\) 之和，求 \(F(10^{18})\mod10^{9}\)。

题解：先来研究负态满足的条件：

手动打表可以发现，负态为所有满足 \(i\ge 0, 0\le j<2^{i},k\ge1,0\le u<2^{i}\) 的 \((2^{i}+j-1,2^{i+1}k+u-1,2^{i+1}k+2^{i}+(j\oplus u)-1)\)。为了方便证明，不妨将三个数都加上 \(1\)，并稍微改写一下式子，得到：负态为所有满足 \(i\ge 0, 0\le j<2^{i},k\ge1,0\le u<2^{i}\) 的 \((2^{i}+(j\oplus u),2^{i+1}k+j,2^{i+1}k+2^{i}+u)\)。这等价于下面的叙述：设 \(a,b,c(a<b<c)\) 的无前导 \(0\) 二进制表示分别为 \(a=a'_{n_{a}}\cdots a'_{0},b=b'_{n_{b}}\cdots b'_{0},c=c'_{n_{c}}\cdots c'_{0}\)，\(b\) 和 \(c\) 最高的不相同的位为第 \(i\) 位，则 \((a,b,c)\) 为负态的充要条件为：\(n_{b}=n_{c}\)，且 \(a=b\oplus c\)。下面我们用归纳法来证明这一结论：

显然 \((1,2,3)\) 为负态，且满足上面的要求。

先证明不满足上面形式的状态是胜态：

• 若 \(n_{b}<n_{c}\)

  • 若 \(n_{a}=n_{b}\)，则 \((a\oplus b,a,b)\) 是一个负态。
  • 若 \(n_{a}<n_{b}\)
    • 若 \(b'_{n_{a}}=1\)，则 \((a,a\oplus b,b)\) 是一个负态。
    • 若 \(b'_{n_{a}}=0\)，则 \((a,b,a\oplus b)\) 是一个负态。

• 若 \(n_{b}=n_{c}\)

  • 若 \(a>b\oplus c\)，则 \((b\oplus c,b,c)\) 是一个负态。

  • 若 \(a<b\oplus c\)

    • 若 \(n_{a}<i\)

      • 若 \(b'_{n_{a}}=1\)，则 \((a,a\oplus b,b)\) 是一个负态。
      • 若 \(b'_{n_{a}}=0\)，则 \((a,b,a\oplus b)\) 是一个负态。

    • 若 \(n_{a}=i\)，我们来证明 \(a\oplus c<b\) 和 \(a\oplus b<c\) 至少有一个成立：

      设 \(a\) 和 \(b\oplus c\) 最高的不相同的位为第 \(j\) 位，则有 \((a'_{n_{c}}\oplus c'_{n_{c}})\cdots(a'_{j+1}\oplus c'_{j+1})=b'_{n_{c}}\cdots b'_{j+1}\) 和 \((a'_{n_{b}}\oplus b'_{n_{b}})\cdots(a'_{j+1}\oplus b'_{j+1})=c'_{n_{b}}\cdots c'_{j+1}\) 均成立。又因为 \(a<b\oplus c\)，所以有 \(a'_{j}=0,b'_{j}\oplus c’_{j}=1\)，故 \(a'_{j}\oplus c'_{j}<b'_{j}\) 和 \(a'_{j}\oplus b '_{j}<c'_{j}\) 至少有一个成立，即 \(a\oplus c<b\) 和 \(a\oplus b<c\) 至少有一个成立。\(\Box\)

      • 若 \(a\oplus c<b\)，则 \((a,a\oplus c,c)\) 是一个负态。
      • 若 \(a\oplus b<c\)，则 \((a,b,a\oplus b)\) 是一个负态。

再证明满足上面形式的状态是负态：

• 若从 \(a\) 中取石子，由于 \(a\) 是由 \(b,c\) 唯一确定的，故取走 \(a\) 中石子后肯定是胜态。
• 若从 \(b\) 中取石子
  • 若取完后 \(b\) 的位数小于 \(c\) 的位数，显然最大的两个数的位数不可能相等，也是一个胜态。
  • 若取完后 \(b\) 的位数等于 \(c\) 的位数，根据异或运算的性质，\(b\) 和 \(c\) 的异或值肯定发生了变化，\(a\) 也肯定不满足负态的要求。
• 若从 \(c\) 中取石子，与 \(b\) 类似可证。\(\Box\)

最后的答案可以通过一个简单的数位 \(dp\) 得到，这里就不再赘述了。

613. Pythagorean Ant

题目大意：有一个边长 \(3,4,5\) 的三角形，一只蚂蚁等概率随机地在三角形中一点，然后等概率选择一个方向沿射线走。问穿过斜边的概率。

题解：其实就是个二重积分，但是第二重好像很恶心的样子，所以就只积了一重，第二重数值积分：

\[ \begin{aligned} &\int\pi-\arctan\frac{3-y}{x}+\arctan\frac{y}{4-x}\mathrm{d}y\\ =&\pi y+x\left[\frac{3-y}{x}\arctan\frac{3-y}{x}-\frac{1}{2}\ln\left(1+(\frac{3-y}{x})^{2}\right)\right]+\\ &(4-x)\left[\frac{y}{4-x}\arctan\frac{y}{4-x}-\frac{1}{2}\ln\left(1+(\frac{y}{4-x})^{2}\right)\right]+C \end{aligned} \]

我爱 python，我爱 scipy！

622. Riffle Shuffles

题目大意：设排列 \(p=(0,n,1,n+1,2,n+2,\cdots,n-1,2n-1)\)，求出所有使得最小循环节为 \(60\) 的 \(2n\) 之和。

题解：显然 \(p\) 与 \(p^{-1}\) 的循环节长度相同，\(p^{-1}=(0,2,4,\cdots,2n-2,1,3,5,\cdots,2n-1)\)。注意到除了 \(2n-1\) 之外，满足 \(p^{-1}(x)=2x\mod(2n-1)\)，但是 \(2n-1\) 本身即成一个环，可以不用考虑。算一算可以发现，最小循环节长度即为最小的使得 \(2^{x}\equiv1\pmod{2n-1}\) 的 \(x\)。要使最小循环节为 \(60\)，那么要有 \(2n-1\mid2^{60}-1\)，\(2n-1\nmid2^{30}-1\)，\(2n-1\nmid2^{20}-1\)，\(2n-1\nmid2^{12}-1\)。稍微算一下即可。

624. Two heads are better than one

题目大意：随机抛一枚硬币，当出现两次正面时停止。设 \(P(n)\) 表示停止时抛硬币的次数能被 \(n\) 整除的概率，求 \(P(10^{18})\mod(10^{9}+9)\)。

题解：设 \(f_{H}(x),f_{T}(x)\) 表示当前未结束，且结尾为 H 或 T 的概率，\(f_{HH}(x)\) 表示当前已经结束的概率。那么可以写出生成函数方程：

\[ \begin{aligned} f_{HH}(x)&=\frac{1}{2}xf_{H}(x)+xf_{HH}(x)\\ f_{H}(x)&=\frac{1}{2}xf_{T}(x)+\frac{1}{2}\\ f_{T}(x)&=\frac{1}{2}x(f_{H}(x)+f_{T}(x))+\frac{1}{2}\\ \end{aligned} \]

\((2)\) 代入 \((3)\) 可得 \(\displaystyle{f_{T}(x)=\frac{\frac{1}{2}+\frac{1}{4}x}{1-\frac{1}{2}x-\frac{1}{4}x^{2}}}\)，代回 \((2)\) 可得 \(\displaystyle{f_{H}(x)=\frac{\frac{1}{2}}{1-\frac{1}{2}x-\frac{1}{4}x^{2}}}\)，代回 \((1)\) 可得 \(\displaystyle{f_{HH}(x)=\frac{\frac{1}{4}x}{(1-\frac{1}{2}x-\frac{1}{4}x^{2})(1-x)}}\)。所求即为 \(\displaystyle{(1-x)f_{HH}(x)=\frac{\frac{1}{4}x}{1-\frac{1}{2}x-\frac{1}{4}x^{2}}}\)。

因此有 \(g_{0}=0,g_{1}=\frac{1}{4},g_{n}=\frac{1}{2}g_{n-1}+\frac{1}{4}g_{n-2}(n\ge2)\)。可以解得特征方程的两个根为 \(654248003,845752011\)。从而解得通项为 \(361699202\times654248003^{n}+638300807\times845752011^{n}\)。最后等比数列求和一下就好了。