Project Euler 813

题目

XOR-Powers

We use $x\oplus y$ to be the bitwise XOR of $x$ and $y$.

Define the XOR-product of $x$ and $y$, denoted by $x \otimes y$, similar to a long multiplication in base $2$, except that the intermediate results are XORed instead of the usual integer addition.

For example, $11 \otimes 11 = 69$, or in base $2$, $1011_2 \otimes 1011_2 = 1000101_2$:

$$\begin{align*} \phantom{\otimes 1111} 1011_2 \\ \otimes \phantom{1111} 1011_2 \\ \hline \phantom{\otimes 1111} 1011_2 \\ \phantom{\otimes 111} 1011_2 \phantom{9} \\ \oplus \phantom{1} 1011_2 \phantom{999} \\ \hline \phantom{\otimes 11} 1000101_2 \\ \end{align*}$$

Further we define $P(n) = 11^{\otimes n} = \overbrace{11\otimes 11\otimes \ldots \otimes 11}^n$. For example $P(2)=69$.

Find $P(8^{12}\cdot 12^8)$. Give your answer modulo $10^9+7$.

解决方案

令$n=8^{12}\cdot 12^8$。

将二进制数$1011_{2}$视为一个用异或加法表示的多项式$1\oplus x\oplus x^3$。那么可以发现，将这个多项式对自身相乘，可以得到新的多项式为$1\oplus x^2\oplus x^6$。将得出来的多项式$1\oplus x^2\oplus x^6$再与自身相乘，那么可以得到$1\oplus x^4\oplus x^{12}$。

由此可以发现规律：$11^{\otimes 2^n}$可以表示成多项式$1\oplus x^{2^n}\oplus x^{3\cdot 2^n}$。也就是说，$P(2^n)=1+2^{2^n}+2^{3\cdot2^n}$。

不难发现，函数$P$满足此性质$P(a+b)=P(a)\otimes P(b)$。因此我们可以把$n$拆分成一个个二进制幂之和，然后再利用这个运算性质，直接将$P(a)$和$P(b)$对应的多项式直接卷积进行计算即可。

代码

N = 12 ** 8 * 8 ** 12
mod = 10 ** 9 + 7


def conv(sa, sb):
    from collections import defaultdict
    mp = defaultdict(int)
    for x in sa:
        for y in sb:
            mp[x + y] ^= 1
    return {k for k, v in mp.items() if v}


su = {0}
st = {0, 1, 3}
while N:
    if N & 1:
        su = conv(su, st)
    st = conv(st, st)
    N >>= 1
ans = sum(pow(2, x, mod) for x in su) % mod
print(ans)