Project Euler 703

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

Project Euler 703

题目

Circular Logic II

Given an integer \(n\), \(n \geq 3\), let \(B=\{\mathrm{false},\mathrm{true}\}\) and let \(B^n\) be the set of sequences of \(n\) values from \(B\). The function \(f\) from \(B^n\) to \(B^n\) is defined by \(f(b_1 \dots b_n) = c_1 \dots c_n\) where:

  • \(c_i = b_{i+1}\) for \(1 \leq i < n\).

  • \(c_n = b_1 \;\mathrm{AND}\; (b_2 \;\mathrm{XOR}\; b_3)\), where \(\mathrm{AND}\) and \(\mathrm{XOR}\) are the logical \(\mathrm{AND}\) and exclusive \(\mathrm{OR}\) operations.

Let \(S(n)\) be the number of functions \(T\) from \(B^n\) to \(B\) such that for all \(x\) in \(B^n\), \(T(x) ~\mathrm{AND}~ T(f(x)) = \mathrm{false}\). You are given that \(S(3) = 35\) and \(S(4) = 2118\).

Find \(S(20)\). Give your answer modulo \(1\,001\,001\,011\).

解决方案

我们将用符号\(\land\)代替\(\text{AND}\)，\(\oplus\)代替\(\text{XOR}\)。考虑有向图\(G=(V,E), E=\{(x,f(x))\mid x\in V\}.\)

因为每个点的出边唯一，所以 \(G\) 是函数图：每个连通分量都由一个有向环 以及若干棵指向环的入树组成。

约束 \(T(x)\land T(f(x))=\text{false}\) 恰好表示：图中任意一条边两端不能同时取 \(\text{true}\)。因此满足 \(T^{-1}(\text{true})\) 是图 \(G\)（视为无向）上的一个独立集，而题目所求的\(S(n)=\#\{T:V\to B \mid T(x)\land T(f(x))=\text{false}\}\)就是独立集的总数。

并且连通分量之间相互独立，于是\(\displaystyle{S(n)=\prod_{\mathcal C\in \mathrm{CC}(G)} S(\mathcal C)},\)这里 \(\text{CC}(G)\) 表示图 \(G\) 的所有连通分量的集合。

先只考虑一棵有根树 \(\mathcal T\)（边从根指向孩子，孩子代表反向前驱），根为 \(u\)。

我们定义两类计数函数：

  • \(\omega(u)\)：在 \(u\) 的整棵子树内，规定 \(u\) 取 \(\text{false}\) 时的合法赋值总数；
  • \(\beta(u)\)：在 \(u\) 的整棵子树内，规定 \(u\) 取 \(\text{true}\)时的合法赋值总数。

设 \(u\) 的孩子集合为 \(\mathrm{Ch}(u)\)，则由独立集条件得到递推：

如果根\(u\)为\(\text{true}\)，那么孩子必须为\(\text{false}\)：

\[ \beta(u)=\prod_{v\in \mathrm{Ch}(u)}\omega(v). \]

如果根\(u\)为\(\text{false}\)，那么孩子可以任意取：

\[ \omega(u)=\prod_{v\in \mathrm{Ch}(u)}(\omega(v)+\beta(v)). \]

叶子点无孩子时，空乘积为 \(1\)，因此\(\omega(u)=\beta(u)=1\)。这两条递推就是树上独立集计数的标准形式，它们完全由约束 \(T(u)\land T(v)=\text{false}\) 推出。

现在回到函数图的一个连通分量 \(\mathcal C\)。设其环为\(c_0\to c_1\to\cdots\to c_{m-1}\to c_0.\)

对环上每个点 \(c_i\)，它除了来自环内的前驱 \(c_{i-1}\) 外，还可能有一些环外前驱，这些前驱向外展开形成若干棵入树。

对每个环点 \(c_i\)，我们把“环外子树”贡献压缩成两个权重：

  • \(\Omega_i\)：规定 \(c_i\) 取\(\text{false}\)时，环外部分的方案数；
  • \(\mathrm{B}_i\)：规定 \(c_i\) 取\(\text{true}\)时，环外部分的方案数。

具体定义为：令 \(\mathrm{Ch}_{\text{off}}(c_i)\) 表示 \(c_i\) 的所有不在环上的前驱点（作为树根），则 \[ \Omega_i=\prod_{v\in \mathrm{Ch}_{\text{off}}(c_i)}(\omega(v)+\beta(v)), \mathrm{B}_i=\prod_{v\in \mathrm{Ch}_{\text{off}}(c_i)}\omega(v). \]

于是整个连通分量的计数问题就化成：在一个长度为 \(m\) 的环上，每个点 \(c_i\) 可以选\(\text{false}\)或\(\text{true}\)；选\(\text{false}\)带来因子 \(\Omega_i\)，选\(\text{true}\)带来因子 \(\mathrm{B}_i\)；相邻两点不能同时为\(\text{true}\)。这是一个带点权的环独立集计数。

先把环切开成链：\(c_0,c_1,\dots,c_{m-1}\)并定义两类前缀计数函数：

  • \(X_i\)：处理到 \(c_i\) 为止，且规定 \(c_i\) 为\(\text{false}\)的总权重和；
  • \(Y_i\)：处理到 \(c_i\) 为止，且规定 \(c_i\) 为\(\text{true}\)的总权重和。

那么对 \(i\ge 1\) 有递推：

  • 当前为\(\text{false}\)，那么前一个可以任意取，有\(X_i=(X_{i-1}+Y_{i-1})\cdot\Omega_i.\)
  • 当前为\(\text{true}\)：前一位必须为\(\text{false}\)，有\(Y_i=X_{i-1}\cdot \mathrm{B}_i.\)

接下来用“首尾相邻”的环约束，做两次条件化：

  • 假设 \(c_0\) 为\(\text{false}\)，初值\(X_0=\Omega_0, Y_0=0.\)递推到末尾后，总贡献为\(W_A=X_{m-1}+Y_{m-1}.\)
  • 假设 \(c_0\) 为\(\text{true}\)，初值\(X_0=0, Y_0=\mathrm{B}_0.\)递推到末尾后，总贡献为\(W_B=X_{m-1}.\)

因此该环（该连通分量）的总贡献为\(S(\mathcal C)=W_A+W_B.\)

接下来考虑自环的情况。若 \(c_0\) 满足 \(f(c_0)=c_0\)，则约束变为\(T(c_0)\land T(c_0)=\text{false} \Longrightarrow T(c_0)=\text{false},\)所以连通分量贡献直接为\(S(\mathcal C)=\Omega_0.\)

将所有连通分量的贡献相乘，得到：\(\displaystyle{S(n)=\prod_{\mathcal C\in \mathrm{CC}(G)} S(\mathcal C)}.\)

代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
from collections import deque

N = 20
MOD = 1001001011

def S(n: int) -> int:
    """
    返回 S(n) mod MOD。
    n >= 3
    """
    sz = 1 << n

    # succ[x] = f(x)
    succ = [0] * sz
    for x in range(sz):
        b1 = x & 1
        b2 = (x >> 1) & 1
        b3 = (x >> 2) & 1
        succ[x] = (x >> 1) | ((b1 & (b2 ^ b3)) << (n - 1))

    # 由于入度 <= 2，用两个槽位存前驱
    indeg = [0] * sz
    pre1 = [-1] * sz
    pre2 = [-1] * sz
    for x, y in enumerate(succ):
        d = indeg[y]
        if d == 0:
            pre1[y] = x
        elif d == 1:
            pre2[y] = x
        indeg[y] = d + 1

    # -------- 1) 用“剥叶子”的方法找出所有环点 --------
    q = deque([i for i in range(sz) if indeg[i] == 0])
    order = []  # 非环点按剥离顺序记录（从叶到根）
    while q:
        u = q.popleft()
        order.append(u)
        v = succ[u]
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)

    in_cycle = [indeg[i] > 0 for i in range(sz)]

    # -------- 2) 在“非环部分”做树 DP 的累积乘积 --------
    # 对每个点 u，我们维护：
    #   prod0[u]  = Π F0(child)
    #   prod01[u] = Π (F0(child)+F1(child))
    # 当所有孩子处理完，则：
    #   F1(u) = prod0[u], F0(u) = prod01[u]
    prod0 = [1] * sz
    prod01 = [1] * sz

    # order 中全是非环点，且是从叶往上剥离，因此可直接把贡献累积到 succ[u]
    for u in order:
        f0 = prod01[u] % MOD
        f1 = prod0[u] % MOD
        v = succ[u]
        prod0[v] = (prod0[v] * f0) % MOD
        prod01[v] = (prod01[v] * (f0 + f1)) % MOD

    # 对环点 c：
    #   A[c] = prod01[c] (c 为false)
    #   B[c] = prod0[c]  (c 为true)
    A = prod01
    B = prod0

    # -------- 3) 对每个环连通分量做“环 DP”并相乘 --------
    visited = [False] * sz
    ans = 1

    for i in range(sz):
        if not in_cycle[i] or visited[i]:
            continue

        # 收集该环（按 succ 方向走一圈）
        cycle = []
        x = i
        while not visited[x]:
            visited[x] = True
            cycle.append(x)
            x = succ[x]

        m = len(cycle)
        if m == 1:
            # 自环：必须为false
            ans = (ans * (A[cycle[0]] % MOD)) % MOD
            continue

        # case 1: first is false
        dp0 = A[cycle[0]] % MOD
        dp1 = 0
        for t in range(1, m):
            u = cycle[t]
            ndp0 = (dp0 + dp1) * (A[u] % MOD) % MOD
            ndp1 = dp0 * (B[u] % MOD) % MOD
            dp0, dp1 = ndp0, ndp1
        ways_first_white = (dp0 + dp1) % MOD

        # case 2: first is true
        dp0 = 0
        dp1 = B[cycle[0]] % MOD
        for t in range(1, m):
            u = cycle[t]
            ndp0 = (dp0 + dp1) * (A[u] % MOD) % MOD
            ndp1 = dp0 * (B[u] % MOD) % MOD
            dp0, dp1 = ndp0, ndp1
        # last cannot be true since first is true
        ways_first_black = dp0 % MOD

        ways_cycle = (ways_first_white + ways_first_black) % MOD
        ans = (ans * ways_cycle) % MOD

    return ans

print(S(N))