CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
===== 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$。<del>随便选一些</del>（其实是有一些规律的）约数筛完后，就只剩下 $30$ 多个可选的元素了。

===== 195. Inscribed circles of triangles with one angle of 60 degrees =====

**题目大意**：大约是要求 $a^{2}-ab+b^{2}=c^{2}$ 的正整数解。

**题解**：部分这样的三元二次齐次不定方程有很漂亮的解法。

$$
\begin{aligned}
&|a-b\omega|^{2}\\
=&|a-\frac{b}{2}-\frac{b\sqrt{3}}{2}i|\\
=&a^{2}-ab+b^{2}
\end{aligned}
$$

其中，$\omega=\frac{1+\sqrt{3}i}{2}$，为 $\omega^{3}+1=0$ 的解。

$$
\begin{aligned}
&(a^{2}-ab+b^{2})^{2}\\
=&|a-b\omega|^{4}\\
=&|a^{2}-2ab\omega+b^{2}\omega^{2}|^{2}\\
=&|a^{2}-b^{2}-(2ab-b^{2})\omega|^{2}\\
=&(a^{2}-b^{2})^{2}-(a^{2}-b^{2})(2ab-b^{2})+(2ab-b^{2})^{2}
\end{aligned}
$$

枚举 $a,b$ 即可得到通解（不会证充分性）。

===== 251. Cardano Triplets =====

**题目大意**：求满足 $a+b+c\le n$，$\sqrt[3]{a+b\sqrt{c}}+\sqrt[3]{a-b\sqrt{c}}=1$ 的正整数 $(a,b,c)$ 数量。

**题解**：不妨设 $a+b\sqrt{c}=(\frac{1}{2}+t\sqrt{c})^{3}$，则 $a-b\sqrt{c}=(\frac{1}{2}-t\sqrt{c})^{3}$。因此有：

$$
\frac{1}{8}+\frac{3}{4}t\sqrt{c}+\frac{3}{2}t^{2}c+t^{3}c\sqrt{c}=a+b\sqrt{c}\\
\frac{1}{8}-\frac{3}{4}t\sqrt{c}+\frac{3}{2}t^{2}c-t^{3}c\sqrt{c}=a-b\sqrt{c}\\
$$

两式相加、相减得

$$
\frac{1}{8}+\frac{3}{2}t^{2}c=a\tag{1}
$$

$$
\frac{3}{4}t+t^{3}c=b\tag{2}
$$

由式 $1$ 可得 $t^{2}$ 是有理数，由式 $2$ 可得 $t$ 是有理数。不妨设 $c$ 无平方因子，那么显然 $t$ 应该有 $\frac{2k+1}{2}(k\in\mathbb{Z})$ 的形式。枚举 $c,t$ 即可。

===== 253. Tidying up =====

**题目大意**：有一个 $1\times n$ 的格子，随机一个 $1\sim n$ 的排列给它染色，求染色过程中连续子段最大值的期望。

**题解**：状压 dp 当然是要 TLE 的啦。

注意到连续的一段 1 可以压缩，除了开头和末尾之外的连续的 0，它们的顺序可以随意交换。

这样复杂度就是 $n$ 的拆分数乘上很多个 $n$ 了。

===== 278. Linear Combinations of Semiprimes =====

$2pqr-pq-pr-qr$。

===== 291. Panaitopol Primes =====

**题目大意**：设 $x,y\in\mathbb{N}^{+}$，$p=\frac{x^{4}-y^{4}}{x^{3}+y{3}}$，求所有 $\le n$ 且为质数的 $p$ 的和。

**题解**：

$$
\begin{aligned}
p&=\frac{(x^{2}+y^{2})(x-y)}{x^{2}-xy+y^{2}}\\
p(x^{2}-xy+y^{2})&=(x^{2}+y^{2})(x-y)
\end{aligned}
$$

因为 $p$ 是质数，所以 $p\mid(x-y)$ 或 $p\mid(x^{2}+y^{2})$，若 $p\mid(x-y)$，那么 $(x^{2}+y^{2})\mid(x^{2}-xy+y^{2})$，矛盾。因此 $p\mid(x^{2}+y^{2})$，$(x-y)\mid (x^{2}-xy+y^{2})$。易得 $(x-y)\mid x^{2}$，$(x-y)\mid xy$，$(x-y)\mid y^{2}$。设 $x^{2}=a(x-y)$，$xy=b(x-y)$，$y^{2}=c(x-y)$。由于 $(x-y)^{2}=a(x-y)-2b(x-y)+c(x-y)$，因此 $(x-y)=a+c-2b$。又由于 $x^{2}y^{2}=ac(x-y)^{2}=b^{2}(x-y)^{2}$，因此 $ac=b^{2}$。故

$$
\begin{aligned}
p&=\frac{(a+c)(x-y)^{2}}{(a+c-b)(x-y)}\\
&=\frac{(a+c)(a+c-2b)}{a+c-b}
\end{aligned}
$$

设 $g=\gcd(a,b,c)$，有

$$
\begin{aligned}
p=g\frac{(a'+c')(a'+c'-2b')}{a'+c'-b'}
\end{aligned}
$$

不妨设**质数** $q\mid\gcd(a'+c'-2b',a'+c'-b')$，那么 $q\mid b'$，又因为 $a'c'=b'^{2}$，因此 $q\mid a'$ 或 $q\mid c'$，从而 $q\mid a',b',c'$。矛盾。同理 $\gcd(a'+c',a'+c'-b')=1$。因此 $(a'+c'-b')|g$，要使 $p$ 为质数，必然有 $a'+c'-2b'=1$ 以及 $g=a'+c'-b'$。联立 $a'c'=b'^{2}$，可得 $\sqrt{a'}-\sqrt{c'}=1$。因此 $p=a'+c'$ 有 $p=n^{2}+(n+1)^{2}(n\in\mathbb{N}^{+})$ 的形式。

===== 319. Bounded Sequences =====

**题目大意**：定义整序列 $\{x_{n}\}$ 满足要求当且仅当：

  * $x_{1}=2$
  * $\forall 1<i\le n$，$x_{i-1}<x_{i}$
  * $\forall 1\le i,j\le n$，$x_{i}^{j}<(x_{j}+1)^{i}$

定义 $f(n)$ 表示长度为 $n$ 的满足要求的序列的数量，求 $f(10^{10})$。

**题解**：

$$
\begin{aligned}
x_{i}^{j}&<(x_{j}+1)^{i}\\
j\ln x_{i}&<i\ln(x_{j}+1)\\
\frac{\ln x_{i}}{i}&<\frac{\ln(x_{j}+1)}{j}
\end{aligned}
$$

那么序列合法，当且仅当 $\exists t$ 使得 $\forall i,\frac{\ln x_{i}}{i}\le t<\frac{\ln(x_{i}+1)}{i}$，即 $e^{it}-1<x_{i}\le e^{it}$，那么 $x_{i}=\lfloor e^{it}\rfloor$。令 $i=1$ 可得 $\ln2\le t<\ln3$。

注意到 $e^{it}$ 关于 $t$ 连续且单调递增，考虑 $t$ 从 $\ln2$ 增加到 $\ln3$ 的过程，显然只有 $\exists i$ 使得 $e^{it}$ 为整数的 $t$ 才会产生一个新的序列。

设 $t=\frac{\ln z}{d}$，$z=\prod_{j=1}^{e}p_{j}^{s_{j}}$，且 $\gcd(s_{1},\cdots,s_{e},d)=1$。那么 $e^{it}$ 为整数，当且仅当 $d|i$。$e^{it}=\prod_{j=1}^{e}p_{j}^{\frac{is_{j}}{d}}$，若 $i\nmid d$，就有 $\frac{d}{\gcd(i,d)}|s_{j}$，矛盾。

不妨设 $g(m)$ 为 $0\le t<m$ 的 $t$ 的数量，则答案为 $g(\ln3)-g(\ln2)$。考虑枚举 $d$：

$$
\begin{aligned}
g(m)&=\sum_{d=1}^{n}\sum_{u\mid d}\mu(u)(e^m)^{\frac{d}{u}}\\
&=\sum_{d=1}^{n}\sum_{u\mid d}\mu(\frac{d}{u})(e^m)^{u}\\
&=\sum_{u=1}^{n}e^{mu}\sum_{u=1}^{\lfloor\frac{n}{u}\rfloor}\mu(u)\\
\end{aligned}
$$

然后杜教筛就可以 $\mathcal{O}(n^{\frac{2}{3}})$ 解决啦。

===== 355. Maximal coprime subset =====

**题目大意**：求 $\{1,2,\cdots,n\}$ 的一个子集，使得其两两互质，且和最大。

**题解**：不容易发现，不会选取某个包含超过两种小质数（$\le\sqrt{n}$）的数。大致是因为大质数非常多，因而能被小质数匹配到的相对很少，因此如果把两个小质数放一起，不如让他们给大质数作贡献（很容易凑到接近 $n$）。那么二分图最大权匹配即可。

===== 379. Least common multiple count =====

**题目大意**：求满足 $x\le y,[x,y]\le n$ 的 $(x,y)$ 对数量。

**题解**：答案为

$$
\begin{aligned}
&\sum_{\gcd=1}^{n}\sum_{x=1}^{n}\sum_{y=1}^{n}[(x,y)=\gcd][\frac{xy}{\gcd}\le n]\\
=&\sum_{\gcd=1}^{n}\sum_{\gcd\mid d}\sum_{x=1}^{n}\sum_{y=1}^{n}\mu(\frac{d}{\gcd})[d\mid(x,y)][\frac{xy}{\gcd}\le n]\\
=&\sum_{\gcd=1}^{n}\sum_{\gcd\mid d}\sum_{d\mid x}\sum_{d\mid y}\mu(\frac{d}{\gcd})[\frac{xy}{\gcd}\le n]\\
=&\sum_{\gcd=1}^{n}\sum_{\gcd\mid d}\mu(\frac{d}{\gcd})S(\lfloor\frac{n}{d^2/\gcd}\rfloor)\\
=&\sum_{\gcd=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{\gcd}\rfloor}\mu(i)S(\lfloor\frac{n}{i^2\gcd}\rfloor)
\end{aligned}
$$

其中 $S(N)$ 表示 $xy\le N$ 的 $xy$ 数量。考虑用类杜教筛求出所有 $S$（本题要带 $\log$，呃，注意到 $S=\sigma$ 的话也不用带 $\log$）。然后枚举 $i$ 根号分块即可，这部分复杂度是 $\sqrt{n}\log n$ 的。

这里就锻炼一下推导能力，min_25 筛应该还快一点。
===== 423. Consecutive die throws =====

**题目大意**：连续投掷一枚均匀骰子 $n$ 次，定义价值为相邻投掷结果相同的数量，定义 $C(n)$ 为价值不超过 $\pi(n)$（小于等于 $n$ 的质数数量）的投掷结果数，$S(n)=\sum_{i=1}^{n}C(n)$。求 $S(5\times10^{7})$。

**题解**：首先求某一价值 $k$ 的方案数 $f(n,k)$。

$$
\begin{aligned}
f(n,k)=&\sum_{|T|=k}(-1)^{|T|-k}{|T|\choose k}{n-1\choose |T|}|\Sigma|^{n-|T|}\\
=&\sum_{|T|=k}(-1)^{|T|-k}\frac{|T|!}{k!(|T|-k)!}\frac{(n-1)!}{|T|!(n-1-|T|)!}|\Sigma|^{n-|T|}\\
=&{n-1\choose k}\sum_{|T|=k}(-1)^{|T|-k}\frac{(n-1-k)!}{(|T|-k)!(n-1-|T|)!}|\Sigma|^{n-|T|}\\
=&{n-1\choose k}\sum_{|T|=k}(-1)^{|T|-k}{n-1-k\choose |T|-k}|\Sigma|^{n-|T|}\\
=&{n-1\choose k}\sum_{t=0}^{n-1-k}(-1)^{t}{n-1-k\choose t}|\Sigma|^{n-t-k}\\
=&{n-1\choose k}|\Sigma|(|\Sigma|-1)^{n-1-k}
\end{aligned}
$$

那么显然有

$$
C(n)=|\Sigma|\sum_{k=0}^{\pi(n)}{n-1\choose k}(|\Sigma|-1)^{n-1-k}
$$

对于这样的组合数前缀和，使用递推即可轻松解决。定义 $F(n,m)=\sum_{k=0}^{m}{n\choose k}(|\Sigma|-1)^{n-k}$，则有

$$
\begin{aligned}
F(n,m)&=\sum_{k=0}^{m}{n\choose k}(|\Sigma|-1)^{n-k}\\
&=\sum_{k=0}^{m}{n-1\choose k-1}(|\Sigma|-1)^{n-k}+\sum_{k=0}^{m}{n-1\choose k}(|\Sigma|-1)^{n-k}\\
&=\sum_{k=0}^{m-1}{n-1\choose k}(|\Sigma|-1)^{n-1-k}+(|\Sigma|-1)\sum_{k=0}^{m}{n-1\choose k}(|\Sigma|-1)^{n-1-k}\\
&=|\Sigma|F(n-1,m)-{n-1\choose m}(|\Sigma|-1)^{n-1-m}
\end{aligned}
$$

===== 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$ 不互质，随便算算就好。实际只需要迭代几百次（很可能中间有一个大质数）。

===== 454. Diophantine reciprocals III =====

**题目大意**：设有不定方程 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$，求满足 $x<y\le N$ 的解数。

**题解**：令 $x=x't,y=y't,(x',y')=1$，则 $\frac{1}{n}=\frac{x'+y'}{tx'y'}$。由于 $(x'+y',x')=1,(x'+y',y')=1$，因此 $(x'+y',x'y')=1$。因此 $x'+y'\mid t$。故 $t$ 的取法有 $\lfloor\frac{N}{y'(x'+y')}\rfloor$ 种。

答案即为

$$
\begin{aligned}
&\sum_{y'=1}^{+\infty}\sum_{x'=1}^{y'-1}[(x',y')=1]\lfloor\frac{N}{y'(x'+y')}\rfloor\\
=&\sum_{d=1}^{+\infty}\mu(d)\sum_{y'=1}^{+\infty}\sum_{x'=1}^{y'-1}[d|(x',y')]\lfloor\frac{N}{y'(x'+y')}\rfloor\\
=&\sum_{d=1}^{+\infty}\mu(d)\sum_{y'=1}^{+\infty}\sum_{x'=1}^{y'-1}\lfloor\frac{\frac{N}{d^{2}}}{y'(x'+y')}\rfloor
\end{aligned}
$$

枚举 $d$，枚举 $y'$，和式根号分块，即可达到较好的时间复杂度。

===== 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)$ 为负态，且满足上面的要求。

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

<HTML><ul></HTML>
<HTML><li style='color:black'></HTML><HTML><p></HTML>若 $n_{b}<n_{c}$<HTML></p></HTML>
<HTML><ul></HTML>
<HTML><li style='color:black'></HTML>若 $n_{a}=n_{b}$，则 $(a\oplus b,a,b)$ 是一个负态。<HTML></li></HTML>
<HTML><li style='color:black'></HTML>若 $n_{a}<n_{b}$
<HTML><ul></HTML>
<HTML><li style='color:black'></HTML>若 $b'_{n_{a}}=1$，则 $(a,a\oplus b,b)$ 是一个负态。<HTML></li></HTML>
<HTML><li style='color:black'></HTML>若 $b'_{n_{a}}=0$，则 $(a,b,a\oplus b)$ 是一个负态。<HTML></li></HTML><HTML></ul></HTML>
<HTML></li></HTML><HTML></ul></HTML>
<HTML></li></HTML>
<HTML><li style='color:black'></HTML><HTML><p></HTML>若 $n_{b}=n_{c}$<HTML></p></HTML>
<HTML><ul></HTML>
<HTML><li style='color:black'></HTML><HTML><p></HTML>若 $a>b\oplus c$，则 $(b\oplus c,b,c)$ 是一个负态。<HTML></p></HTML><HTML></li></HTML>
<HTML><li style='color:black'></HTML><HTML><p></HTML>若 $a<b\oplus c$<HTML></p></HTML>
<HTML><ul></HTML>
<HTML><li style='color:black'></HTML><HTML><p></HTML>若 $n_{a}<i$<HTML></p></HTML>
<HTML><ul></HTML>
<HTML><li style='color:black'></HTML>若 $b'_{n_{a}}=1$，则 $(a,a\oplus b,b)$ 是一个负态。<HTML></li></HTML>
<HTML><li style='color:black'></HTML>若 $b'_{n_{a}}=0$，则 $(a,b,a\oplus b)$ 是一个负态。<HTML></li></HTML><HTML></ul></HTML>
<HTML></li></HTML>
<HTML><li style='color:black'></HTML><HTML><p></HTML>若 $n_{a}=i$，我们来证明 $a\oplus c<b$ 和 $a\oplus b<c$ 至少有一个成立：<HTML></p></HTML>
<HTML><p></HTML>设 $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$<HTML></p></HTML>
<HTML><ul></HTML>
<HTML><li style='color:black'></HTML>若 $a\oplus c<b$，则 $(a,a\oplus c,c)$ 是一个负态。<HTML></li></HTML>
<HTML><li style='color:black'></HTML>若 $a\oplus b<c$，则 $(a,b,a\oplus b)$ 是一个负态。<HTML></li></HTML><HTML></ul></HTML>
<HTML></li></HTML><HTML></ul></HTML>
<HTML></li></HTML><HTML></ul></HTML>
<HTML></li></HTML><HTML></ul></HTML>

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

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

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

===== 495. Writing n as the product of k distinct positive integers =====

**题目大意**：设 $S(n,m)$ 为将 $n$ 表示成 $m$ 个互不相同的整数乘积的方案数，求 $S(n,m)$。

**题解**：考虑容斥。枚举 $m$ 的所有划分，表示每个子集中的所有整数相等，子集间是否相等没关系。注意到各个不同的位置本质相同，因此不需要真的枚举划分，而只需要枚举划分数即可。复杂度为 $P(m)$。注意最后答案要除以一个阶乘。若划分为整个集合，其容斥系数为

$$
C(m)=\begin{cases}
&1&(m=1)\\
&-\sum_{P\text{ is a partition of M},P\neq\{M\}}\text{coe}(P)&(m>1) 
\end{cases}
$$

其中，$\text{coe}(P)$ 表示划分 $P$ 的容斥系数。若划分并非是整个集合，那么 $\text{coe}(P)=\prod_{Q\in P}C(|Q|)$。可以证明，这样的容斥系数恰使得所有数互不相同的方案贡献为 $1$，其它方案贡献为 $0$。

计算某个方案时，可以注意到是一个无限背包 dp。

**update**：事实上，可以证明 $C(m)=(-1)^{m-1}(m-1)!$。考虑数学归纳法，枚举 $1$ 所在的子集。注意到 $m\ge2$ 时，

$$
\begin{aligned}
&\sum_{P\text{ is a partition of M}}\text{coe}(P)\\
=&\sum_{P\text{ is a partition of M},P\neq\{M\}}\text{coe}(P)\\
&-\sum_{P\text{ is a partition of M},P\neq\{M\}}\text{coe}(P)\\
=&0
\end{aligned}
$$

因此 $C(m)=-C(m-1)\cdot{m-1\choose m-2}\cdot1=(-1)^{m-1}(m-1)!$。

===== 515. Dissonant Numbers =====

**题目大意**：对一个质数 $p$，定义 $S(i,p,0)=i^{-1}\bmod p$。定义 $S(n,p,k)=\sum_{i=1}^{n}S(i,p,k-1)$。求 $S(p-1,p,a)$。

**题解**：可得

$$
\begin{aligned}
&S(p-1,p,a)\\
=&\sum_{i=1}^{p-1}{a+p-2-i\choose a-1}\cdot\frac{1}{i}\\
=&-\sum_{i=1}^{p-1}{a+p-2-i\choose a-1}\cdot\frac{1}{p-i}\\
=&-\sum_{i=1}^{p-1}{a-2+i\choose a-1}\cdot\frac{1}{i}\\
=&-\sum_{i=1}^{p-1}\frac{(a-2+i)!}{(a-1)!(i-1)!}\cdot\frac{1}{i}\\
=&-\sum_{i=1}^{p-1}\frac{(a-2+i)!}{(a-1)!i!}\\
=&-\frac{1}{a-1}\sum_{i=1}^{p-1}\frac{(a-2+i)!}{(a-2)!i!}\\
=&-\frac{1}{a-1}\sum_{i=1}^{p-1}{a-2+i\choose i}\\
=&-\frac{1}{a-1}\left({a+p-2\choose p-1}-1\right)\\
=&\frac{1}{a-1}
\end{aligned}
$$

===== 545. Faulhaber’s Formulas =====

[[https://en.wikipedia.org/wiki/Von_Staudt%E2%80%93Clausen_theorem|Von Staudt–Clausen theorem]]

===== 581. 47-smooth triangular numbers =====

[[https://en.wikipedia.org/wiki/St%C3%B8rmer%27s_theorem|Størmer’s theorem]]

===== 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}$。最后等比数列求和一下就好了。

===== 692. Siegbert and Jo =====

**题目大意**：一个游戏有 $n$ 颗石子，两人轮流拿，每人最少拿一颗，最多拿上一个人拿的两倍。第一次拿没有限制。设 $f(n)$ 表示先手最少拿几颗保证必胜，求 $\sum_{k=1}^{n}f(k)$。

**题解**：这题出过很多次了，主要是 $f(n)$ 的定义给了我另一个视角看待这个问题。$f(n)$ 本身其实是可以直接计算的，不需要分析胜负态。$f(n)$ 即为最小的 $i$，使得 $2i<f(n-i)$。答案打表找规律即可。

===== 711. Binary Blackboard =====

**题目大意**：给出一个正整数 $n$，并在黑板上写下 $n$ 的二进制表示，之后先手后手轮流在黑板上写正整数的二进制表示，并保证和不超过 $2n$，不能写时游戏结束。如果 $1$ 的数量为奇数，先手胜，否则后手胜。分析胜负态。

**题解**：定义 $f(n)=\text{bitcnt}(n)$。若 $\exists x+y=n$，$y=2^{f(y)}-1,f(n)+f(x)+f(y)\equiv1\pmod{2}$，那么显然先手必胜，先手写上 $x$ 后，不论后手写什么，先手写上 $y$ 减它即可获胜。

考虑 $n$ 最后连续的 $1$ 的数量 $d$，分类讨论（以下都是所有位不全为 $1$ 的情况）：

  * 若 $d$ 为奇数，且**前面**存在一个偶数位 $b$ 为 $1$，那么令 $x=n-2^{b}+1$，$f(n)+f(x)+f(y)=2f(n)-1-d+1+b$ 为一个奇数，因此先手胜。
  * 若 $d$ 为偶数，且**前面**存在一个奇数位 $b$ 为 $1$，同理先手胜。

若全部位都为 $1$，后手只需把所有数拿走就可以获胜了。

剩余两种情况，不会证了。。。

  * 若 $d$ 为奇数，且**前面**所有为 $1$ 的位均为奇数，先手胜。
  * 若 $d$ 为偶数，且**前面**所有为 $1$ 的位均为偶数，先手负。

===== 741. Binary grid colouring =====

**题目大意**：在一个 $n\times n$ 的网格上黑白染色，使得每行每列均恰好有两个格子是黑的，求在**旋转和对称**等价的意义下不同的方案数。

**题目大意**：显然需要使用 burnside 引理，总共需要计算 $5$ 种情况，分别是无限制、旋转 $90^{\circ}/270^{\circ}$ 相同、旋转 $180^{\circ}$ 相同、沿对角线对称、水平或竖直对称。

解决这道题的关键思想是将其看做一个图的邻接矩阵（但是行顺序有关系），由于每一列有 $2$ 个黑格子，相当于每个点的度数都是 $2$，也就是说图是由若干个环组成的。确定好边集后，行之间还可以任意排列，但是需要注意二元环的两条边交换没有意义，故每个二元环需要除 $2$。总而言之，通过枚举 $1$ 所在的环，可以列出 $dp$ 方程：

$$
\begin{aligned}
dp_i&=\sum_{j=2}^{i}\frac{A_{i-1}^{j-1}}{2}\cdot dp_{i-j}\\
&=(i-1)!\sum_{j=2}^{i}\frac{dp_{i-j}}{(i-j)!}
\end{aligned}
$$

答案是 $n!dp_{n}$，可以 $\mathcal{O}(n)$ 计算。

旋转 $90^{\circ}/270^{\circ}$ 时，若 $n$ 为奇数，由于黑格子的数量模 $4$ 总不为 $0$，因此无解。$n$ 为偶数的时候，考虑左上一半格子，它旋转 $4$ 下后要每行每列各有 $2$ 个黑格子，可以证明这等价于第 $i$ 行加第 $i$ 列的黑格子数为 $2$。考虑第 $1$ 行第 $1$ 列的放置方式，分类讨论一下可以 dp 解决。

旋转 $180^{\circ}$ 时，考虑将第 $i$ 列和第 $n+1-i$ 列看作同一个点。$n$ 为偶数时与第一种情况大体相同，区别在于可以有自环，并且第 $i$ 列和第 $n+1-i$ 列是两种不同的方案。$n$ 为奇数时较复杂。首先不妨将中间行和中间列的黑点都放在两侧。第一行有两种情况，填 $1/n$ 或填其它。填 $1/n$ 时，归约到了 $n-3$ 的情况。否则不妨设填了 $2$，那么相当于 $1$ 和 $2$ 的度只能是 $1$，那么可以枚举一下 1-2 的这一条链中间的点，然后也能归约到偶数的情况。

沿对角线对称时与旋转 $90^{\circ}/270^{\circ}$ 类似，而沿水平/垂直对称最为简单。

时间复杂度 $\mathcal{O}(n)$。
CVBB ACM Team

用户工具

站点工具

页面工具
