CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:zhongzihao:project_euler [2021/01/22 22:13]
toxel 创建
+++ 2020-2021:teams:intrepidsword:zhongzihao:project_euler [2021/02/20 21:05] (当前版本)
toxel add 379
@@ 行 55: / 行 55: @@
 由式 $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 =====
@@ 行 129: / 行 139: @@
 然后杜教筛就可以 $\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 =====
@@ 行 135: / 行 204: @@
 **题解**：可以猜测会有大段连续的 $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 =====
@@ 行 141: / 行 228: @@
 **题解**：方程化简为 $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 =====
@@ 行 155: / 行 244: @@
 <HTML><ul></HTML>
-<HTML><li></HTML><HTML><p></HTML>若 $n_{b}<n_{c}$<HTML></p></HTML>
+<HTML><li style='color:black'></HTML><HTML><p></HTML>若 $n_{b}<n_{c}$<HTML></p></HTML>
 <HTML><ul></HTML>
-<HTML><li></HTML>若 $n_{a}=n_{b}$，则 $(a\oplus b,a,b)$ 是一个负态。<HTML></li></HTML>
+<HTML><li style='color:black'></HTML>若 $n_{a}=n_{b}$，则 $(a\oplus b,a,b)$ 是一个负态。<HTML></li></HTML>
-<HTML><li></HTML>若 $n_{a}<n_{b}$
+<HTML><li style='color:black'></HTML>若 $n_{a}<n_{b}$
 <HTML><ul></HTML>
-<HTML><li></HTML>若 $b'_{n_{a}}=1$，则 $(a,a\oplus b,b)$ 是一个负态。<HTML></li></HTML>
+<HTML><li style='color:black'></HTML>若 $b'_{n_{a}}=1$，则 $(a,a\oplus b,b)$ 是一个负态。<HTML></li></HTML>
-<HTML><li></HTML>若 $b'_{n_{a}}=0$，则 $(a,b,a\oplus b)$ 是一个负态。<HTML></li></HTML><HTML></ul></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></HTML><HTML><p></HTML>若 $n_{b}=n_{c}$<HTML></p></HTML>
+<HTML><li style='color:black'></HTML><HTML><p></HTML>若 $n_{b}=n_{c}$<HTML></p></HTML>
 <HTML><ul></HTML>
-<HTML><li></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$，则 $(b\oplus c,b,c)$ 是一个负态。<HTML></p></HTML><HTML></li></HTML>
-<HTML><li></HTML><HTML><p></HTML>若 $a<b\oplus c$<HTML></p></HTML>
+<HTML><li style='color:black'></HTML><HTML><p></HTML>若 $a<b\oplus c$<HTML></p></HTML>
 <HTML><ul></HTML>
-<HTML><li></HTML><HTML><p></HTML>若 $n_{a}<i$<HTML></p></HTML>
+<HTML><li style='color:black'></HTML><HTML><p></HTML>若 $n_{a}<i$<HTML></p></HTML>
 <HTML><ul></HTML>
-<HTML><li></HTML>若 $b'_{n_{a}}=1$，则 $(a,a\oplus b,b)$ 是一个负态。<HTML></li></HTML>
+<HTML><li style='color:black'></HTML>若 $b'_{n_{a}}=1$，则 $(a,a\oplus b,b)$ 是一个负态。<HTML></li></HTML>
-<HTML><li></HTML>若 $b'_{n_{a}}=0$，则 $(a,b,a\oplus b)$ 是一个负态。<HTML></li></HTML><HTML></ul></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></HTML><HTML><p></HTML>若 $n_{a}=i$，我们来证明 $a\oplus c<b$ 和 $a\oplus b<c$ 至少有一个成立：<HTML></p></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></HTML>若 $a\oplus c<b$，则 $(a,a\oplus c,c)$ 是一个负态。<HTML></li></HTML>
+<HTML><li style='color:black'></HTML>若 $a\oplus c<b$，则 $(a,a\oplus c,c)$ 是一个负态。<HTML></li></HTML>
-<HTML><li></HTML>若 $a\oplus b<c$，则 $(a,b,a\oplus b)$ 是一个负态。<HTML></li></HTML><HTML></ul></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>
@@ 行 192: / 行 281: @@
 最后的答案可以通过一个简单的数位 $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 =====
@@ 行 271: / 行 411: @@
 **题目大意**：显然需要使用 burnside 引理，总共需要计算 $5$ 种情况，分别是无限制、旋转 $90^{\circ}/270^{\circ}$ 相同、旋转 $180^{\circ}$ 相同、沿对角线对称、水平或竖直对称。
-解决这道题的关键思想是将其看做一个图的邻接矩阵（但是顺序有关系），由于每一列有 $2$ 个黑格子，相当于每个点的度数都是 $2$，也就是说图是由若干个环组成的。确定好边集后，行之间还可以任意排列，但是需要注意二元环的两条边交换没有意义，故每个二元环需要除 $2$。总而言之，通过枚举 $1$ 所在的环，可以列出 $dp$ 方程：
+解决这道题的关键思想是将其看做一个图的邻接矩阵（但是行顺序有关系），由于每一列有 $2$ 个黑格子，相当于每个点的度数都是 $2$，也就是说图是由若干个环组成的。确定好边集后，行之间还可以任意排列，但是需要注意二元环的两条边交换没有意义，故每个二元环需要除 $2$。总而言之，通过枚举 $1$ 所在的环，可以列出 $dp$ 方程：
 $$
@@ 行 280: / 行 420: @@
 $$
+答案是 $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

用户工具

站点工具

页面工具