Volume 04

151. Paper sheets of standard sizes: an expected-value problem

用5元组分别表示各种大小的纸片的数目作为状态进行dp就好了.

152. Writing as a sum of inverse squares

对于一个奇素数, 如果某些数是他的倍数, 那么这些数加起来之后的最简分数的分母一定不是的倍数, 否则永远不可能凑出. 经过测试发现, 只有这些素数是有用的, 其中如果要用, 那么和也要必选. 分为选不选进行爆搜就好了.

153. Investigating Gaussian Integers

可以观察到, 如果, 那么就是的约数.

考虑枚举的那些数, 那么是的约数, 当且仅当.

令, , 那么题目中的. 显然和可以求出来的, 那么也就出来了.

154. Exploring Pascal's pyramid

那个式子展开之后, 其中前面的系数是, 暴力枚举下和即可.

155. Counting Capacitor Circuits

令为用了恰好个等容量电容能构成的集合, 可以用十分暴力的方法递推出来, 然后. 似乎也可以算出前10项, 然后去oeis上找答案.

156. Counting Digits

可以观察到如果是答案, 那么也很可能是一个答案. 可以猜想, 当比较大的时候, 下一个合法的也比大许多. 于是可以根据的大小调整step的值, 进行暴力枚举. 计算是很经典的数位dp, 这里不表.

讨论帖里面说的值大约为, 稍微比这个小一点应该就好了.

157. Solving the diophantine equation

令, 那么上式可以化简成.

考虑到, 可以得到, 如果已知, 那么满足上式的数目就是. 暴力枚举, 对分解质因数.

158. Exploring strings for which only one character comes lexicographically after its neighbour to the left

对于某个, 答案就是, 于是答案就是.

159. Digital root sums of factorisations

这个显然可以递推出来, , 复杂度.

论坛里面提供了一个直接计算的方法, 伪代码如下:

def mdrs(n):
  prime_list = factorize(n)
  tuple = [0] * 9
  for p in prime_list:
    tuple[digital_root(p)] += 1
  res = 0
  while tuple[2] > 0 and tuple[4] > 0:
    tuple[2] -= 1
    tuple[4] -= 1
    res += 8
  while tuple[2] > 2:
    tuple[2] -= 3
    res += 8
  while tuple[3] > 1:
    tuple[3] -= 2
    res += 9
  while tuple[2] > 0 and tuple[3] > 0:
    tuple[2] -= 1
    tuple[3] -= 1
    res += 6
  for i in xrange(9):
    res += i * tuple[i]
  return res

160. Factorial trailing digits

末尾的个数可以用这个公式求出来. 令, 那么. 不妨考虑中国剩余定理, 分别求出和. 由于后面这个值肯定是, 可以只考虑前面的.

考虑把写成这种形式, 其中. 令, 那么, 其中, 也可以递归下去, 于是, 注意到只有这两个解, 于是.

考虑, 于是. 求出来后中国剩余定理合并一下就好了.

161. Triominoes

状态压缩dp就好了.

162. Hexadecimal numbers

随便dp下就好了.

163. Cross-hatched triangles

利用前两项去oeis上可以找到公式, 其中.

164. Numbers for which no three consecutive digits have a sum greater than a given value

随便数位dp下就好了.

165. Intersections

线段求出交点, 放到set里面搞一搞就好了.

166. Criss Cross

考虑这个数分别是, 可以列出若干个方程, 最后消元之后发现只有个是有用的, 于是显然只要确定了个数, 剩下个数就确定了.

不妨枚举, 令, 那么

还有

没有确定, 再枚举下

, 那么

这样

个数都确定了, 剩下只要检查

和

是否都成立即可, 其他等式都已经满足了.

167. Investigating Ulam sequences

可以证明, 的差分序列最终会变成一个有周期的. 然后观察可以知道, 这个序列恰好只有个偶数(一个是, 另一个不妨设为), 于是在这两个偶数之后, 其他数肯定由偶数+奇数得到的, 也就是说重复的和最多只有2个.

于是, 就可以用优先队列维护所有候选的可能在的数, 每次新加入一个数到, 那么在优先队列中新插入两个数和, 这样就可以很快得到.

然后处理出差分序列, 用kmp找周期就好了, 最长的周期有那么大, 尽量搞出比较多的项数再求周期比较好.

论坛里面有人指出的差分序列的周期长度是差不多. 这篇paper里面证明了这些东西. 似乎还存在的算法可以求出差分序列的周期.

168. Number Rotations

设这个数有位, 那么这个数可以表示为, 旋转后这个数为, 令, 化简下得到, 可以发现都是个位数, 于是暴力枚举就好了.

169. Exploring the number of different ways a number can be expressed as a sum of powers of

找出前几项, 可以到oeis上找到公式,

170. Find the largest to pandigital that can be formed by concatenating products

这个数一定是开头, 于是只需要枚举后面部分, 之后枚举划分, 求出划分后的数, 那个乘数一定是这些数的最大公约数的约数, 然后可以发现这个数最多不超过, 且一定是的倍数. 利用上面条件, 暴力枚举.

171. Finding numbers for which the sum of the squares of the digits is a square

由于, , 于是随便数位dp下就好了.

172. Investigating numbers with few repeated digits

枚举每个数字出现的次数, 先判断数字个数之和恰好是18, 之后枚举第一个数字是什么, 然后用组合数统计下答案就好了, 需要注意不能有前导零.

173. Using up to one million tiles how many different "hollow" square laminae can be formed?

令里外的正方形边长分别是, 那么有并且和同奇偶, , 那么显然最大不超过, 暴力枚举, 然后解出的范围即可.

174. Counting the number of "hollow" square laminae that can form one, two, three, ... distinct arrangements

根据#173的答案可以发现, 合法的hollow square不多, 于是暴力枚举所有合法的, 统计出现的次数就好了.

175. Fractions involving the number of different ways a number can be expressed as a sum of powers of 2

通过oeis查表可以知道, 依次构成了Stern-Brocot Tree的每一项, 已知树上某一项, 可以利用欧几里得算法求出路径.

通过oeis查表知道, 如果, 那么, 然后题目给的数字比较小, 随便手算下就得出答案了.

177. Integer angled Quadrilaterals

令分别为, 已知的情况下, 如果满足, 那么就是一个合法的四边形.

令的交点为, , 然后枚举, 可以求出, 剩下还没有确定. 考虑正弦定理, 令, 那么, 之后利用余弦定理就可以知道的长度, 然后再次用正弦定理求出的值, 就可以用求出了. 判断和是不是整数, 以及检查下度数条件是否满足即可. 需要判断四边形是否相似, 直接用最小表示就好了, 需要注意的是需要用个角做最小表示, 只用个会不对.