# 判断操作后字符串中的数字是否相等

> source: 文章/string-digits-equal/index.md

leetcode
- [3461.判断操作后字符串中的数字是否相等I](https://leetcode.cn/problems/check-if-digits-are-equal-in-string-after-operations-i/?envType=daily-question&envId=2025-10-23)
- [3463.判断操作后字符串中的数字是否相等II](https://leetcode.cn/problems/check-if-digits-are-equal-in-string-after-operations-ii/description/)

这两道题的题意完全一样，真正的区别只在数据范围：

- `3461` 的长度不大，可以直接模拟
- `3463` 的长度很大，必须直接计算最终结果

也正因为题面几乎没变，所以 `3463` 会给人一种“看起来还是模拟题，结果一写就超时”的感觉。


## 模拟

对于 `3461`，直接按题意模拟即可。每一轮把相邻两个数字相加并对 `10` 取模，直到只剩两个字符

```go
func hasSameDigits(s string) bool {
    arr := []byte(s)

    // 每轮把当前长度 -1，直到只剩两个字符
    for length := len(arr); length > 2; length-- {
        for i := 0; i < length - 1; i++ {
            arr[i] = (arr[i] - '0' + arr[i+1] - '0') % 10 + '0'
        }
    }
    return arr[0] == arr[1]
}
```

这段代码的时间复杂度是 `O(n^2)`。放在 `3461` 上没有问题，但到了 `3463` 就一定超时


## 从模拟到组合数

如果原字符串是：

```text
a b c d e
```

做一轮之后变成：

```text
a+b, b+c, c+d, d+e
```

再做一轮：

```text
a+2b+c, b+2c+d, c+2d+e
```

再做一轮：

```text
a+3b+3c+d, b+3c+3d+e
```

可以看到，系数正好是杨辉三角，也就是组合数

所以，假设原串长度是 `n`，做完 `n - 2` 轮后，最后剩下的两个数分别是：

$$
A = \sum_{i=0}^{n-2}\binom{n-2}{i}s[i] \pmod{10}
$$

$$
B = \sum_{i=0}^{n-2}\binom{n-2}{i}s[i+1] \pmod{10}
$$

题目要求判断最后两位是否相等，也就是：

$$
A = B \pmod{10}
$$

把它移到一边，就是：

$$
\sum_{i=0}^{n-2}\binom{n-2}{i}(s[i] - s[i+1]) \equiv 0 \pmod{10}
$$

这就是整题的核心。

原来那一轮一轮的相邻求和，最终都可以等价成一次组合数加权求和。也就是说，现在我们不能再盯着操作过程本身，而要直接去算最后这一次线性组合


## 为什么要拆开算

难点在于模数是 `10`，而：

```text
10 = 2 * 5
```

它不是质数，所以不能直接像常见组合数模板那样在 `mod 10` 下计算

正确做法是拆开算，先算 `mod 2`，再算 `mod 5`，最后把两个结果合起来判断，因为一个数模 `10` 等于 `0`，当且仅当：

1. 它模 `2` 等于 `0`
2. 它模 `5` 也等于 `0`

所以问题自然就拆成了两部分，先求这整个式子在 `mod 2` 下的值，再求它在 `mod 5` 下的值，只要这两个结果都为 `0`，原式在 `mod 10` 下也就为 `0`。


## 先算 `C(m, i) mod 2`

我们要算的是：

$$
\binom{n-2}{i} \bmod 2
$$

这里用 Lucas 定理，但在 `mod 2` 的时候它会变得非常简单：

$$
\binom{m}{i} \bmod 2 = 1
\quad \Longleftrightarrow \quad
i\text{ 的二进制每一位都没有超过 }m
$$

换成位运算就是：

```go
(i &^ m) == 0
```

其中 `m = n - 2`。

也就是说，只有当 `i` 的二进制位是 `m` 的子集时，组合数模 `2` 才等于 `1`。这一部分几乎可以直接用位运算完成


## 再算 `C(m, i) mod 5`

接下来是：

$$
\binom{m}{i} \bmod 5
$$

这里继续用 Lucas 定理把 `m` 和 `i` 写成五进制：

$$
m = (\dots m_2 m_1 m_0)_5
$$

$$
i = (\dots i_2 i_1 i_0)_5
$$

那么有：

$$
\binom{m}{i} \bmod 5
=
\prod \binom{m_k}{i_k} \bmod 5
$$

由于每一位都只会是 `0..4`，只需要预处理一个很小的组合数表：

```text
C(a, b), 0 <= a, b < 5
```

也就是：

```text
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
```

如果某一位上 `i_k > m_k`，那么这一项直接为 `0`。因此 `C(m, i) mod 5` 可以在 `O(log_5 n)` 时间内算出


## 整体做法

设：

```text
m = n - 2
d[i] = s[i] - s[i+1]
```

我们需要判断：

$$
\sum_{i=0}^{m}\binom{m}{i}d[i] \equiv 0 \pmod{10}
$$

于是分别维护：

$$
sum2 = \sum \binom{m}{i}d[i] \pmod{2}
$$

$$
sum5 = \sum \binom{m}{i}d[i] \pmod{5}
$$

最后判断：

- `sum2 == 0`
- `sum5 == 0`

两者同时为 `0`，答案就是 `true`

## 代码

```go
func hasSameDigits(s string) bool {
	n := len(s)
	m := n - 2

	// 预处理小组合数表，供 Lucas(mod 5) 使用
	C := [5][5]int{}
	for i := 0; i < 5; i++ {
		C[i][0] = 1
		C[i][i] = 1
		for j := 1; j < i; j++ {
			C[i][j] = C[i-1][j-1] + C[i-1][j]
		}
	}

	lucas5 := func(n, k int) int {
		res := 1
		for n > 0 || k > 0 {
			ni := n % 5
			ki := k % 5
			if ki > ni {
				return 0
			}
			res = res * C[ni][ki] % 5
			n /= 5
			k /= 5
		}
		return res
	}

	sum2, sum5 := 0, 0

	for i := 0; i <= m; i++ {
		d := int(s[i]-'0') - int(s[i+1]-'0')

		// C(m, i) mod 2
		if (i &^ m) == 0 {
			sum2 = (sum2 + d) & 1
		}

		// C(m, i) mod 5
		c5 := lucas5(m, i)
		sum5 = (sum5 + c5*d) % 5
	}

	if sum5 < 0 {
		sum5 += 5
	}

	return sum2 == 0 && sum5 == 0
}
```


## 复杂度

- 时间复杂度：`O(n log_5 n)`
- 空间复杂度：`O(1)`

## 总结

这题最关键的不是代码细节，而是先完成下面这一步转换：

```text
反复模拟相邻求和
-> 观察系数变化
-> 发现是杨辉三角
-> 写成组合数求和
-> 因为模 10 不是质数，拆成 mod 2 和 mod 5
-> 用 Lucas 定理快速计算
```

一旦看出这里，剩下就是 Lucas 定理和拆模数的实现问题了
