Volume 05

201. Subsets with a unique sum

用背包计算出和为的数的方案数就好了, 可以用__int128, 也可以用long long, 然后自然溢出. 更合理的方法是找几个大质数取模, 然后crt合并.

202. Laserbeam

把平面用正三角形平铺, 把放在原点, 那么其他可能是点的坐标满足. 显然, 反射就是相当于, 从原点到这个点和条线段有交, 并且这个点没有被挡住, 也就是说.

可以很容易算出来, 从原点到点的连线恰好经过条线段, 也就是要解下面这个方程的解数:

论坛里面给出了一个公式解, 令, 那么答案就是, 其中是欧拉函数, 是满足模3余2的质因子个数.

203. Squarefree Binomial Coefficients

暴力分解阶乘的质因数就好了.

204. Generalised Hamming Numbers

总个数不是很多, 于是可以一个质数一个质数地扩展上去.

205. Dice Game

背包计算出摇出和为的概率和, 答案就是.

206. Concealed Square

直接暴力枚举那个要求的数就好了, 在内.

207. Integer partition equations

令, 那么. 如果是整数, 显然是的幂次. 从小到大枚举, 维护的幂次的个数, 以及当前的值.

208. Robot Walks

观察下可以知道, 总共有种不同的圆弧, 一个显然的结论就是这些圆弧的数目都要相同才能构成一个环路. 于是可以以当前每种圆弧数目和当前位于那个圆弧上作为状态, 转移比较显然, 这里不表.

其实上面的状态还可以简化, 是不需要的, 我们不妨假设永远在圆弧上, 往左和往右转实际上就是把这个元组左移和右移(类似相对运动这种), 于是状态最多只有种.

209. Circular Logic

考虑枚举这个6元组的值, 显然和不能同时为0. 把当做图中的一个节点, 那么就在和之间连一条边.

实际上就是求这个-SAT的方案数, 画出图来可以发现, 这个图是由几个环组成的, 长度分别为. 对于长度为的环, 我们很容易得出答案就是.

210. Obtuse Angled Triangles

分别从和做线段的垂线, 显然答案被分成了部分. 左右两部分十分简单, 就是

至于中间部分, 显然要求出以中点为圆心, 半径为的圆内整点个数. 直接暴力枚举坐标计算即可. 最后还需要减去和共线的那些点.

计算圆内整点个数实际上有的做法, 需要参考论坛里面这个帖子.

211. Divisor Square Sum

是个积性函数, . 可以直接筛出来, 也可以用上面公式, 先线性筛出所有质数, 以及每个数的最小质因子, 然后暴力分解质因数就好了.

212. Combined Volume of Cuboids

枚举当前坐标的值, 在上做矩形并就好了.

213. Flea Circus

每只跳蚤都是独立的, 于是可以枚举每只跳蚤, 计算出步以后在每个位置的概率. 然后每个格子也是独立的, 只需要计算出每个格子步以后不被占据的概率, 然后全部加起来就好了. 也就是说答案就是

214. Totient Chains

线性筛计算出, 然后暴力枚举totient chain的长度就好了.

215. Crack-free Walls

表示当前处理到第行, 状态为的方案数, 用三进制储存, 然后dfs暴力转移就好了.

216. Investigating the primality of numbers of the form

暴力枚举每个, 然后用miller-rabin测试跑的还是挺快的. 出题人用的是筛法, 考虑枚举奇质数, 那么当且仅当. 显然中最多只有两个解和, 那么就可以筛去所有的和, 这些显然都是合数.

217. Balanced Numbers

令和表示前位数位和为(前半部分加, 后半部分减)的个数以及数字和, 转移只需要枚举当前位是什么数字就好了.

218. Perfect right-angled triangles

用了神奇的Tree of Primitive Pythagorean Triples, 最后答案居然是0. 证明如下:

由于, 可以令其中, 显然又是一对互素勾股数. 于是令, 那么显然, . 由于, 那么或者, 所以.

219. Skew-cost coding

考虑从根节点开始, 给做儿子代价加, 给右儿子代价加, 那么最后叶子的代价和就是这种code的, 于是为了达到最小, 显然每次需要选择一个最小的叶子进行扩展. 然后可以注意到每次权值的种类不多, 于是维护一个的元组, 不断扩展就好了.

220. Heighway Dragon

搜了搜Dragon curve, 可以在Wolfram MathWorld上找到. 令, 那么阶的Dragon curve是. 递归结构很明显了, 于是只要随便算算就好了.

221. Alexandrian Integers

打表可以在oeis上找到Alexandrian Integers的形式为. 枚举一个的上界(大概)就够了, 然后暴力分解质因数, 枚举出所有, 求出所有可行的Alexandrian Integers, 排个序, 找出第大, 可是这样非常慢. 有若干个加速的方法:

第一个是用(叫做Brahmagupta–Fibonacci identity), 考虑对题目中定义直接化简, 可以得到, 本来做法和上面一样是要枚举的约数. 但是可以令, 那么然后的可以用Stern-Brocot tree生成.

上面方法可以进一步简化, 令, 其实可以变成(考虑Stern-Brocot tree相邻两项就可以得到), 当往左走的时候, , 会得到

222. Sphere Packing

令表示当前使用的球集合为, 最后一个球为的最小长度, 枚举下一个没有被使用的球, 计算贡献就好了.

223. Almost right-angled triangles I

移项可以得到, 枚举, 对做质因数分解, 枚举它的约数就可以求出和. 虽然这个方法挺快的, 但还是不够快, 参考#221, 我们可以猜测也可以用一些转移直接求出来.

事实上这个转移矩阵就是Tree of Primitive Pythagorean Triples里面的三个矩阵, 只需要考虑初始值即可. 这里详细讲了如何构造这三个矩阵The Trinary Tree(s) underlying Primitive Pythagorean Triples.

224. Almost right-angled triangles II

和#223类似, 用Tree of Primitive Pythagorean Triples里面的三个矩阵就好了, 初始值为. 事实上, 这个矩阵应该适用与任何吧.

225. Tribonacci non-divisors

大约猜了猜的周期差不多是, 于是枚举每个, 暴力枚举周期内的数, 判断是否存在.

226. A Scoop of Blancmange

这个圆和这条曲线的一个交点是, 然后二分出另一个交点, 计算可以暴力枚举, 直到不够精度(大概就差不多了)为止. 然后再用simpson积分搞一下.

227. The Chase

显然只和当前两个骰子的最短距离有关. 令表示, 当前两个骰子最短距离为的期望步数, 枚举转移, 然后可以列出方程组, 高斯消元解一下就好了.

228. Minkowski Sums

对于给出来的两个凸包和, 求他们的Minkowski sum很简单, 把所有边按照极角排序, 然后依次连接起来就好了. 对于题目中的极角序可以用整数来表示, 就是. 于是这题事实上就是求集合枚举所有分数 , 去个重.

229. Four Representations using Squares

开了个大小为的bitset, 然后暴力枚举. 一些优化的地方, 当且仅当可以分解成或者; 当且仅当可以分解成. 这个帖子有详细的说明.

230. Fibonacci Words

随便递归下就好了.

231. The prime factorisation of binomial coefficients

直接暴力枚举质因数分解就好了.

232. The Race

这个显然只能倒着分析, 令表示当前两人的得分分别是和, 且当前是第二个人掷骰子的获胜概率, 我们知道边界. 考虑枚举第二个人要掷次骰子, 得到分的概率是, 那么我们可以得出 注意当的时候, 中间哪项要变成, 因为已经轮不到第一个选手掷骰子了.

233. Lattice points on a circle

可以找到这样的一个规律, , 其中 .

于是推导一下知道, 可行的有. 筛出素数, 暴力枚举就好了.

234. Semidivisible numbers

大概只要筛出不超过的素数就好了, 然后枚举和, 我们可以知道对应这对的所在的区间为. 容斥算出不同同时被和整除的数之和就好了.

235. An Arithmetic Geometric sequence

显然可以二分答案, 然后用Horner's method就可以保证精度相对较高地计算.

236. Luxury Hampers

考虑枚举Beluga Caviar中坏掉的数目, 那么实际上就可以算出来了, 同理我们可以知道的值, 这样就可以确定出所有可能的, 然后检查第二个条件就好了. 通过计算可以发现, 这样大概有的计算量, 显然跑不出来, 然后考虑折半枚举, 分别枚举出和的组合, 问题变成求出是否存在, 其中, ,,. 把式子化简得到 于是只要维护出左右的值, 分别排个序, 归并检查是否有相同就好了. 这样的计算量大概只有.

237. Tours on a 4 x n playing board

.

238. Infinite string tour

打表可以发现这个字符串的周期大概是级别, 一个周期内的数字和大概是级别的, 那么考虑暴力计算出 , 显然有, 随便计算下就好了. 由于这个数列有够随机, 暴力计算的过程十分快, 似乎的范围是左右.

239. Twenty-two Foolish Primes

枚举哪3个质数位置不变, 剩下来就是要计算表示长度为的排列中, 前个数一定要错排的方案数. 用容斥很容易得到

240. Top Dice

表示前个骰子, 最后一个数字是, 到目前位置已经出现了次, 以及当前和为的方案数, 考虑枚举下一个位置填, 那么:

1. 当的时候,
2. 当的时候, .

241. Perfection Quotients

不是很大, 最大大概吧, 于是可以考虑枚举, 搜出可行的答案. 注意到, , 于是有, 于是可以考虑每次枚举, 给当前结果乘上. 显然, 我们每次都把先中消掉, 也就是选择那些能使新得到中没有因子的. 这样每次枚举的基本上都是互不相同的. 为了确实保证每个没有被重复枚举, 加个visited数组保存那些素数被枚举过了就好了(可以猜测可行的素数范围不是很大, 大概以内). 这样爆搜可以在s内出解.

242. Odd Triplets

首先通过打表知道, 只有的时候才是有解的, 然后忽略, 把其他数按照二进制分组, 先个, 然后个, 然后, 依次类推. 然后可以注意到, 第的Odd Triplets实际上是就是第组以及第组翻个倍组成的, 那么第组的Odd Triplets数目.

我们大概就有了一个递归结构, 随便谢谢就好了.

243. Resilience

显然, 为了使最小, 最优答案是连续的素数相乘, 然后再乘一个较小的数 . 于是暴力枚举乘到哪个素数, 然后暴力枚举那个就好了.

244. Sliders

用表示红色, 表示蓝色, 加上空白格子的位置信息就可以表示一个棋盘的配置, 于是随便dp一下就好了.

245. Coresilience

简单推导一下可以知道必须是奇数, 然后我打出内的所有合法解, 发现必须是squarefree的. 于是考虑暴力枚举所有squarefree的, 判断是否可行.

不妨假设当前枚举到, 一个合法解, 那么有, 移项化简得到, 首先, 我们是知道的范围的, . 于是我们就可以得到一个合法的的范围. 很显然的范围比较小, 于是通过枚举可以求出, 然后再素数判定下就好了. 而且, 一定要是偶数(因为是偶数, 是奇数), 可以再减少一般枚举量.

官方做法是特殊处理semiprime(那些case), 对于其他square free的, 用上述方法做. 对于semiprime, 有, 于是

枚举的约数可以用#216的那种筛法, 可以做到.

246. Tangents to an ellipse

参考了这里的公式, 可以很方便计算的值, 然后考虑枚举, 显然对于固定的, 越大, 角度越小, 于是就可以二分了. 似乎点的轨迹构成了另一个椭圆, 也许求出方程会更方便.

247. Squares under a hyperbola

先暴力dfs计算出的最小边长, 然后再一边dfs, 暴力计算出有多少正方形边长大于等于.

248. Numbers for which Euler’s totient function equals

注意到, 由于, 于是我们要找出满足的那些素数, 这些都是候选的质因子, 考虑, 还需要加入, , , 这些数, 然后爆搜就好了. 满足条件的数最多只有个, 全部都搜出来也没事.

也可以考虑用优先队列维护, 然后从小到大扩展每个数.

249. Prime Subset Sums

他们的和最大不超过, 于是直接背包就好了.

250.

表示前个数选某些数构成子集, 和对250取模的值为的方案数, 直接转移就好了.