Vibe Coding.

观察发现这是一个矩阵问题,可以把情况压缩到一个向量里面.

于是懒得自己写就问gpt要一个脚本.

prompt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3似数
将正整数n视为数字串，记f(n)为能被3整除的n的非空子串数目。例如，数字串”2573”有10个非空子串，其中有三个能被3整除，分别是57、573和3，因此f(2573)=3。

如果f(n)能被3整除，则称n为3似数。

记F(d)为d位数中3似数的个数。例如，F(2)=30，F(6)=290898。

求F(10^5)并将你的答案对1e9+7取余。

我的思路是构建一个长度81的向量,代表当前遍历到的位数为i时,所有子区间和模3余012的结果的数量再模3分别是0,1,2的时候的数字的数量.(比如向量0代表当前遍历到第i位时,所有子区间模3余1的区间为0(再模3),模3余2的区间为0(再模3),模3余0的区间个数为0(再模3)的数字的个数,容易发现这是3*3*3*3=81维的,不是243维的)
然后对于每一位填0-9,这可以构成一个27*27的转移矩阵,然后快速幂矩阵乘法计算出10^5次方.

你需要特别注意,当前遍历到i位时的向量代表了各种情况下数字的个数,这个是对1e9+7取模的,不是对3取模的,所以矩阵就是81维,绝对不是243维的.

你需要构建这个矩阵最后求解,请注意初始的向量因为d位数的限制不能为0,而转移矩阵可以为0.
而且初始向量是1位数,你实际要求的是d-1次方.
请给我python脚本。

ChatGPT

1
2
3
4
5
6
7
我已经实现并运行了完整的 Python 脚本（含矩阵构建、快速幂、校验），并计算出结果：

* F(2) = 30（与题目给定一致）
* F(6) = 290898（与题目给定一致）
* F(10^5) mod (1e9+7) = **884837055**

我也把用于计算的脚本保存为 `/mnt/data/compute_F_3like.py`（笔记本里可见完整代码片段）。下面我把完整可直接运行的脚本粘贴给你（与你看到的运行版完全一致）——可直接保存为 `.py` 并运行：
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
MOD = 10**9 + 7

# Build mapping between state (s0,s1,s2,t0) with s0,s1,s2,t0 in {0,1,2} and index 0..80
states = []
idx = {}
for s0 in range(3):
    for s1 in range(3):
        for s2 in range(3):
            for t0 in range(3):
                st = (s0,s1,s2,t0)
                idx[st] = len(states)
                states.append(st)
N = len(states)
assert N == 81

def next_state(st, digit):
    s0,s1,s2,t0 = st
    x = digit % 3
    s = [s0,s1,s2]
    sprime = [ (s[(k - x) % 3] + (1 if x == k else 0)) % 3 for k in range(3) ]
    t0p = (t0 + sprime[0]) % 3
    return (sprime[0], sprime[1], sprime[2], t0p)

# Build transition matrix M (N x N) such that v_next = M * v_current
def build_M():
    M = [[0]*N for _ in range(N)]
    for j, st in enumerate(states):
        for d in range(10):
            stp = next_state(st, d)
            i = idx[stp]
            M[i][j] = (M[i][j] + 1) % MOD
    return M

# Matrix multiply
def mat_mult(A, B):
    p = len(A); q = len(A[0]); r = len(B[0])
    C = [[0]*r for _ in range(p)]
    for i in range(p):
        Ai = A[i]
        Ci = C[i]
        for k in range(q):
            aik = Ai[k]
            if aik == 0: continue
            Bk = B[k]
            mul = aik
            for j in range(r):
                Ci[j] = (Ci[j] + mul * Bk[j]) % MOD
    return C

# Matrix-vector multiply
def mat_vec_mult(A, v):
    p = len(A); q = len(A[0])
    res = [0]*p
    for i in range(p):
        s = 0
        Ai = A[i]
        for j in range(q):
            s = (s + Ai[j] * v[j]) % MOD
        res[i] = s
    return res

# Matrix exponentiation
def mat_pow(M, e):
    def identity(n):
        I = [[0]*n for _ in range(n)]
        for i in range(n):
            I[i][i] = 1
        return I
    result = identity(N)
    base = [row[:] for row in M]
    while e > 0:
        if e & 1:
            result = mat_mult(base, result)
        base = mat_mult(base, base)
        e >>= 1
    return result

# Build M once
M = build_M()

# initial vector v1 for 1-digit numbers (leading digit cannot be 0): digits 1..9
v1 = [0]*N
for d in range(1,10):
    st = (0,0,0,0)  # before first digit
    stp = next_state(st, d)
    v1[idx[stp]] = (v1[idx[stp]] + 1) % MOD

# function to compute F(d)
def F(d):
    if d == 1:
        return sum(v1[i] for i,st in enumerate(states) if st[3] == 0) % MOD
    Mp = mat_pow(M, d-1)
    vd = mat_vec_mult(Mp, v1)
    ans = 0
    for i, st in enumerate(states):
        if st[3] == 0:
            ans = (ans + vd[i]) % MOD
    return ans

# Quick checks
print("F(2) =", F(2))      # 30
print("F(6) =", F(6))      # 290898

# Final answer
d = 10**5
print("F(10^5) mod 1e9+7 =", F(d))
1
如果你想我把完整脚本打包成可下载的 `.py` 文件，或者解释代码中某一步（例如状态设计、为什么只需记录后三个后缀计数模3和 T0 模3），我可以继续说明。

fun fact

丢给gemini2.5 flash换了三次提示词反复强调,gemini一直输出243维的矩阵.可能是没用gemini 2.5 pro.