Project Euler 759
题目
A squared recurrence
relation
The function is defined for
all positive integers as follows:
It can be proven that is
integer for all values of .
The function is defined as
.
For example, and
.
Find . Give your
answer modulo .
解决方案
暴力枚举出 的前几项,在 OEIS 中查询得到结果为 A245788。
令 表示 的二进制表示中有多少个 ,那么按照题意,。
将 进行改写:
也就是说,问题转化成枚举 ,求 以内的所有数中,满足 的所有 之和。
将 写成一个长度为 的二进制数字符串 ,也就是有 。
令中间状态 分别表示如下含义:有多少个 位有前导 0 的数,其二进制有 个 ,并等于由字符串 表示的数。令状态 表示 中的所有数之和。令状态 表示 中的所有数的平方和。
不难发现,如果 ,那么 , 的值则为 这一个字符串的二进制数,并且 ;否则 。
状态 的意义在于规定了答案严格在界限上的情况。而接下来定义的状态 则是严格不在界限上的情况。
令状态 表示有多少个 位有前导 0 的数,其数位和为 ,并严格小于由字符串 表示的数。令状态 表示 中的所有数之和, 表示 。中的所有数的平方和。
那么可以先写出 的状态转移方程:
其中, 表示示性函数,如果 内的表达式为真,那么值为 ,否则为 。方程的前两项,如果之前的状态已经是严格小于 的数,那么接下来无论在后面拼接一个 还是一个 ,都是严格小于的;对于第三项而言,如果之前取的值都是严格等于的,那么接下来如果 ,那么可以拼接一个 ,从而达到严格小于的情况。
根据上面的思想,不难写出 和 :
需要注意的是,对于 的状态转移方程最后一行的前三项,系数是 ,来自于平方式 。
计算完成后,得到最终答案为:
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| N = 10 ** 16 mod = 1000000007 d = list(map(int, list(bin(N)[2:]))) l = len(d) c = [[[0, 0] for _ in range(l + 1)] for _ in range(l)] s = [[[0, 0] for _ in range(l + 1)] for _ in range(l)] t = [[[0, 0] for _ in range(l + 1)] for _ in range(l)] c[0][1][1] = s[0][1][1] = t[0][1][1] = 1 c[0][0][0] = 1 cnt = 1 for i in range(1, l): cnt += d[i] c[i][cnt][1] = 1 s[i][cnt][1] = s[i - 1][cnt - d[i]][1] * 2 + d[i] t[i][cnt][1] = t[i - 1][cnt - d[i]][1] * 4 + s[i - 1][cnt - d[i]][1] * d[i] * 4 + d[i] c[i][0][0] = 1 s[i][0][0] = t[i][0][0] = 0 for j in range(1, l + 1): c[i][j][0] = c[i - 1][j - 1][0] + c[i - 1][j][0] s[i][j][0] = s[i - 1][j - 1][0] * 2 + c[i - 1][j - 1][0] + s[i - 1][j][0] * 2 t[i][j][0] = t[i - 1][j - 1][0] * 4 + s[i - 1][j - 1][0] * 4 + c[i - 1][j - 1][0] + t[i - 1][j][0] * 4 if d[i] == 1: c[i][j][0] += c[i - 1][j][1] s[i][j][0] += s[i - 1][j][1] * 2 t[i][j][0] += t[i - 1][j][1] * 4
ans = 0 for i in range(l + 1): ans += sum(t[-1][i]) * i * i ans %= mod print(ans)
|