绳子题目

1. f((n,1,c1),(m,n+1,c2),k) 的值 只与 n,c1,m,c2,k 这五个变量有关，与 (n,1,c1) 和 (m,n+1,c2) 内部的黑边具体在哪里无关
2. 给出简洁的可以求 f((n,1,c1),(m,n+1,c2),k) 与 n,c1,m,c2,k 这五个变量 的式子

证明与公式推导

1. 证明 $f((n,1,c_1),(m,n+1,c_2),k)$ 的值仅与 $n, c_1, m, c_2, k$ 有关

• 若相邻两节点属于同一条原绳子，且原绳子中这两节点间的边为黑色，则新边为黑色；
• 否则，新边为白色。

• 第一条绳子中，边 $i$-$i+1$（$1 \leq i \leq n-1$) 被保留当且仅当在新序列中节点 $i$ 和 $i+1$ 相邻（即无第二条绳子的节点插入其间）。
• 第二条绳子中，边 $j$-$j+1$（$n+1 \leq j \leq n+m-1$) 被保留当且仅当在新序列中节点 $j$ 和 $j+1$ 相邻（即无第一条绳子的节点插入其间）。

• 在交错过程中，第一条绳子的所有边在对称性下不可区分（即任意两条边被保留的概率分布相同），第二条绳子同理。
• 固定 $|A| = a$ 和 $|B| = b$ 时，子集 $A$ 在所有大小为 $a$ 的子集中均匀分布，子集 $B$ 在所有大小为 $b$ 的子集中均匀分布，且 $A$ 与 $B$ 独立（由序列构造的对称性保证）。
• 因此，$K$ 的分布仅依赖于 $c_1$ 和 $c_2$（即黑边总数），而不依赖于黑边的具体位置。具体地，对于任意两个具有相同 $n, c_1$ 的第一条绳子配置和相同 $m, c_2$ 的第二条绳子配置，$K$ 的分布相同，故 $f((n,1,c_1),(m,n+1,c_2),k)$ 仅由 $n, c_1, m, c_2, k$ 决定。

2. 求 $f(n, c_1, m, c_2, k)$ 的简洁表达式

• $r_0 = n - a$ 为第一条绳子节点在新序列中形成的游程数（连续 $0$ 的段数），则被保留边数 $|A| = a = n - r_0$。
• $r_1 = m - b$ 为第二条绳子节点在新序列中形成的游程数（连续 $1$ 的段数），则被保留边数 $|B| = b = m - r_1$。
• 约束条件：$|r_0 - r_1| \leq 1$（由序列游程性质决定），即 $|(n - a) - (m - b)| \leq 1$。
• 权重函数 $w(a,b)$ 表示满足 $|A| = a$ 和 $|B| = b$ 的序列数中的起始字符因子： $$w(a,b) = \begin{cases} 2 & \text{if } n - a = m - b \\ 1 & \text{otherwise} \end{cases}$$ 该因子源于序列起始字符的选择（当 $r_0 = r_1$ 时有两种起始选择，否则只有一种）。

• $S$ 是 $A$ 中黑色边数量，服从超几何分布：从 $n-1$ 条边中选 $a$ 条保留，其中 $c_1$ 条为黑边。
• $T$ 是 $B$ 中黑色边数量，服从超几何分布：从 $m-1$ 条边中选 $b$ 条保留，其中 $c_2$ 条为黑边。
• 由于对称性，$S$ 和 $T$ 独立。

• $\binom{c_1}{s} \binom{n - 1 - c_1}{a - s}$ 是选择 $a$ 条保留边中恰有 $s$ 条黑边的方式数。
• $\binom{c_2}{k - s} \binom{m - 1 - c_2}{b - (k - s)}$ 是选择 $b$ 条保留边中恰有 $k - s$ 条黑边的方式数。
• 二项式系数在参数无效时定义为 $0$（如负下标或上标小于下标）。

验证示例

• 例1：$n=2, m=2, c_1=1, c_2=1, k=1$
  计算得 $f=2$（序列 $0110$ 和 $1001$ 各贡献 $1$)，与公式一致。
• 例2：$n=2, m=2, c_1=1, c_2=1, k=0$
  计算得 $f=2$（序列 $0101$ 和 $1010$)，与公式一致。
• 例3：$n=3, m=1, c_1=1, c_2=0, k=0$
  计算得 $f=1$（序列 $0100$)，与公式一致（详细计算略，符合对称性）。

优化后的公式与 O(n+m) 查询算法

1. 证明 f 仅与 n, c1, m, c2, k 有关（略）

2. 优化公式与 O(n+m) 查询

• r：新序列中连续段总数（游程数），满足 $|r - 2\max(r_0, r_1)| \leq 1$，其中 $r_0 = n - a$, $r_1 = m - b$。
• X：第一条绳子中被切断的黑边数（即未保留）。
• Y：第二条绳子中被切断的黑边数。
• 保留的黑边总数：$k = (c_1 - X) + (c_2 - Y) = c_1 + c_2 - (X + Y)$。

• 权重函数 $w(r_0, r_1)$： $$w(r_0, r_1) = \begin{cases} 2 \cdot \binom{n-1}{r_0-1} \binom{m-1}{r_1-1} & \text{if } r_0 = r_1 \\ \binom{n-1}{r_0-1} \binom{m-1}{r_1-1} & \text{if } |r_0 - r_1| = 1 \end{cases}$$
• 组合数 $C(r_0, r_1, T)$ （$T = c_1 + c_2 - k$）： $$C(r_0, r_1, T) = \sum_{x=\max(0, T - c_2)}^{\min(c_1, T)} \binom{c_1}{x} \binom{n-1-c_1}{r_0-1-x} \binom{c_2}{T-x} \binom{m-1-c_2}{r_1-1-(T-x)}$$

1. 预处理：计算阶乘和逆阶乘表，范围至 $N = \max(n, m) + \max(c_1, c_2) + k$。时间复杂度 $O(N)$，空间 $O(N)$。
2. 枚举有效 (r_0, r_1) 对：
   • $r_0$ 范围：$1$ 到 $n$。
   • 对每个 $r_0$，$r_1$ 取值：$\{r_0-1, r_0, r_0+1\} ∩ [1, m]$。
   • 有效对数量为 $O(n + m)$，因为 $r_0$ 有 $O(n)$ 个值，每个 $r_0$ 对应 $O(1)$ 个 $r_1$。
3. 计算 C(r_0, r_1, T)：
   • $T = c_1 + c_2 - k$ 固定。
   • $x$ 的范围：$\max(0, T - c_2)$ 到 $\min(c_1, T, r_0-1, r_0-1 + c_1 - (n-1))$，但实际非零项数 $O(1)$（由二项式系数边界限制）。
   • 每项二项式系数 $O(1)$ 查询（查预处理表）。
   • 内层求和 $O(1)$ 时间（常数项数）。
4. 总复杂度：$O(n + m)$ 每查询（预处理 $O(N)$ 一次）。

def f(n, c1, m, c2, k):
    T = c1 + c2 - k  # 需切断的黑边总数
    total = 0
    for r0 in range(1, n+1):  # r0: 第一条绳子的段数
        for r1 in [r0-1, r0, r0+1]:
            if r1 < 1 or r1 > m: 
                continue
            if abs(r0 - r1) > 1: 
                continue
            
            # 计算权重 w(r0, r1)
            weight = binom(n-1, r0-1) * binom(m-1, r1-1)
            if r0 == r1:
                weight *= 2
            
            # 计算组合数 C(r0, r1, T)
            comb_val = 0
            x_min = max(0, T - c2, r0-1 - (n-1-c1))  # 考虑白边数量约束
            x_max = min(c1, T, r0-1)                   # 考虑黑边和总切断数
            for x in range(x_min, x_max+1):
                y = T - x
                if y < 0 or y > c2 or (r1-1 - y) < 0 or (r1-1 - y) > (m-1-c2):
                    continue
                term = binom(c1, x) * binom(n-1-c1, r0-1-x) 
                term *= binom(c2, y) * binom(m-1-c2, r1-1-y)
                comb_val += term
            
            total += weight * comb_val
    return total

• 常数时间二项式系数：通过预处理阶乘和逆阶乘，每次查询 $O(1)$。
• 枚举范围小：$r_0$ 有 $n$ 个值，$r_1$ 每 $r_0$ 仅 $3$ 个候选，总枚举数 $O(n + m)$。
• 内层求和项数少：$x$ 的范围受二项式系数自然限制（无效项为$0$），实际循环次数为常数（$≤ min(c_1, c_2, T) + 1$），在 $O(1)$ 时间内完成。