Project Euler 760

发表于 分类于 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 3 分钟

Project Euler 760

题目

Sum over Bitwise Operators

Define \[\displaystyle g(m,n) = (m\oplus n)+(m\lor n)+(m\wedge n)\] where \(\oplus, \lor, \wedge\) are the bitwise XOR, OR and AND operator respectively.

Also set \[\displaystyle G(N) = \sum_{n=0}^N\sum_{k=0}^n g(k,n-k)\] For example, \(G(10) = 754\) and \(G(10^2) = 583766\).

Find \(G(10^{18})\). Give your answer modulo \(1\,000\,000\,007\).

解决方案

给定关于运算\(\oplus,\lor,\land\)的真值表：

\[\begin{array}{|c|c|c|c|c|} \hline m & n & \oplus & \lor & \land \\ \hline 0 & 0 & 0 & 0 & 0\\ \hline 0 & 1 & 1 & 1 & 0\\ \hline 1 & 0 & 1 & 1 & 0\\ \hline 1 & 1 & 0 & 1 & 1\\ \hline \end{array}\]

因此，\(g(m,n)=2 (n\lor m)\)。于是问题等价于求\(\displaystyle{G(N)=2\sum_{n=0}^{N}\sum_{k=0}^{n} (k\lor(n-k)).}\)令\(\displaystyle{A(n)=\sum_{k=0}^{n} g(k,n-k),}\)则\(\displaystyle{G(N)=\sum_{n=0}^{N}A(n).}\)

由 \(g(m,n)=2(m\lor n)\) 得\(\displaystyle{A(n)=2\sum_{k=0}^{n} (k\lor(n-k)).}\)接下来推导 \(A(n)\) 的递推式，再由此推导 \(G(N)\) 的递推式。

可见有如下按位性质（对任意非负整数 \(x,y\)）：\((2x)\lor(2y)=2(x\lor y),(2x+1)\lor(2y+1)=2(x\lor y)+1,(2x)\lor(2y+1)=2(x\lor y)+1.\)

\(A(2n)\)

我们首先计算 \(A(2n)\)。将 \(k\) 按奇偶拆开：

  • 当 \(k=2t\)，则 \(2n-k=2(n-t)\)，于是\(g(2t,2(n-t))=2((2t)\lor(2(n-t)))=2\cdot 2(t\lor(n-t))=4(t\lor(n-t)).\)
  • 当 \(k=2t+1\)，则\(2n-k=2n-(2t+1)=2(n-t-1)+1,\)

于是有\(g(2t+1,2(n-t-1)+1)=2((2t+1)\lor(2(n-t-1)+1))=2(2(t\lor(n-t-1))+1)=4(t\lor(n-t-1))+2.\)

因此 \[ \begin{aligned} A(2n) &=\sum_{t=0}^{n} 4(t\lor(n-t)) +\sum_{t=0}^{n-1}(4(t\lor(n-t-1))+2)\\ &=2A(n)+2A(n-1)+2n. \end{aligned} \]

\(A(2n + 1)\)

现在计算 \(A(2n+1)\)同样拆奇偶：

  • 当 \(k=2t\)，则 \(2n+1-k=2(n-t)+1\)，有\(g(2t,2(n-t)+1)=2((2t)\lor(2(n-t)+1))=2(2(t\lor(n-t))+1)=4(t\lor(n-t))+2.\)
  • 当 \(k=2t+1\)，则 \(2n+1-k=2(n-t)\)，有\(g(2t+1,2(n-t))=2((2t+1)\lor(2(n-t)))=2(2(t\lor(n-t))+1)=4(t\lor(n-t))+2.\)

两部分的 \(t\) 都从 \(0\) 到 \(n\)，所以

\[ \begin{aligned} A(2n+1) &=\sum_{t=0}^{n}(4(t\lor(n-t))+2)+\sum_{t=0}^{n}(4(t\lor(n-t))+2)\\ &=8\sum_{t=0}^{n}(t\lor(n-t))+4(n+1)\\ &=4A(n)+4n+4. \end{aligned} \]

综上得到关于\(A(n)\)的递推：

\[\begin{aligned} A(0)&=0,\\ A(1)&=4,\\ A(2n)&=2A(n)+2A(n-1)+2n,\\ A(2n+1)&=4A(n)+4n+4. \end{aligned} \]

接下来计算\(G(2n)\) 与 \(G(2n+1)\)的递推。

\(G(2n)\)

我们将 \(G(2n)\) 按奇偶项拆分，得到：\(\displaystyle{G(2n)=\sum_{k=0}^{n}A(2k)+\sum_{k=0}^{n-1}A(2k+1).}\)那么有：

\[ \begin{aligned} \sum_{k=0}^{n}A(2k) &=A(0)+\sum_{k=1}^{n}(2A(k)+2A(k-1)+2k)\\ &=2\sum_{k=1}^{n}A(k)+2\sum_{k=1}^{n}A(k-1)+2\sum_{k=1}^{n}k\\ &=2G(n)+2G(n-1)+n(n+1).\\ \sum_{k=0}^{n-1}A(2k+1) &=\sum_{k=0}^{n-1}(4A(k)+4k+4)\\ &=4G(n-1)+4\cdot\frac{(n-1)n}{2}+4n\\ &=4G(n-1)+2n^2+2n. \end{aligned} \]

相加得 \[ \begin{aligned} G(2n) &=(2G(n)+2G(n-1)+n(n+1))+(4G(n-1)+2n^2+2n)\\ &=2G(n)+6G(n-1)+3n(n+1). \end{aligned} \]

\(G(2n+1)\)

可见，\(G(2n+1)=G(2n)+A(2n+1).\) 又因为 \(A(n)=G(n)-G(n-1)\)，且 \(A(2n+1)=4A(n)+4n+4\)，于是

\[ \begin{aligned} G(2n+1) &=2G(n)+6G(n-1)+3n(n+1)+4(G(n)-G(n-1))+4n+4\\ &=6G(n)+2G(n-1)+3n^2+7n+4. \end{aligned} \]

综上得到关于\(G(n)\)的递推：

\[\begin{aligned} G(0)&=0,\\ G(1)&=4,\\ G(2n)&=2G(n)+6G(n-1)+3n(n+1),\\ G(2n+1)&=6G(n)+2G(n-1)+3n^2+7n+4. \end{aligned} \]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from functools import cache

MOD = 1000000007
N = 10 ** 18

@cache
def G(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 4
    if n & 1 == 0:
        m = n // 2
        return (2 * G(m) + 6 * G(m - 1) + 3 * m * (m + 1)) % MOD
    else:
        m = n // 2
        return (6 * G(m) + 2 * G(m - 1) + (3 * m * m + 7 * m + 4)) % MOD
print(G(N))