codeforces：F. Kirei and the Linear Function【暴力优化 + 避开大数运算 + 避开str切片转int】

分析

核心就是找到v1 * v + v2 == k (mod 9)
那就固定一个v1看看有没有v2 = k - v1 * v
实际上vi可以通过滑动窗口看长度为w的余数
实际上v也可以通过切片直接获取
然后看看固定v1，求出v2后，我们用一个dict记录每个余数的idx
如果v1v2都有长度且不同，那么都取第一个；如果相同，就取第一第二个
然后拿到最小的v1，v2

优化点

1.vi可以通过滑动窗口看长度为w的余数涉及大数运算，因为w最大可以到10**5
由于我们是在mod 9的意义下的，所以数字可以转成数位和，用一个前缀和维护即可

2.v也可以通过切片直接获取涉及字符串切片转int，复杂度实际o(r-l+1) -> o(n)
同理，由于是mod 9意义，转成数位和，用前缀和优化成o（1）即可

Ac code

import sys
from collections import defaultdict
from itertools import accumulate
input = sys.stdin.readline

def solve():
    s = input().strip()
    n = len(s)
    w, m = list(map(int, input().split()))
    d = defaultdict(list)

    # ---------------------------
    # slide window
    # big number operation: bad!
    # ---------------------------

    # curr = 0
    # for i in range(n):
    #     if i < w:
    #         curr = curr * 10 + int(s[i])
    #     else:
    #         d[curr % 9].append(i - w)
    #         curr -= int(s[i - w]) * 10 ** (w - 1)
    #         curr = curr * 10 + int(s[i])
    # d[curr % 9].append(n - w)

    # %3 or %9 the same as the sum of the digits
    lst = [int(c) for c in s]
    preSum = list(accumulate(lst, initial = 0))

    # avoid big number, use sum of digits
    for i in range(n - w + 1):
        u = (preSum[i + w] - preSum[i]) % 9
        d[u].append(i)

    #print(d)
    for _ in range(m):
        l, r, k = list(map(int, input().split()))

        # ---------------------------
        # slice + int => o(r - l + 1) => bad as o(N)
        # ---------------------------
        # v_l_r = int(s[l - 1:r]) % 9
        # use preSum instead
        v_l_r = (preSum[r] - preSum[l - 1]) % 9
        # v2 = ki - v1 * v_l_r
        L1, L2 = n + 1, n + 1
        for v1 in range(9):
            if len(d[v1]) > 0:
                v2 = (k - v1 * v_l_r) % 9
                if v1 != v2 and len(d[v2]) > 0:
                    # choices.append([d[v1][0], d[v2][0]])
                    if d[v1][0] < L1:
                        L1, L2 = d[v1][0], d[v2][0]
                    elif d[v1][0] == L1 and d[v2][0] < L2:
                        L1, L2 = d[v1][0], d[v2][0]
                elif v1 == v2 and len(d[v1]) > 1:
                    # choices.append([d[v1][0], d[v1][1]])
                    if d[v1][0] < L1:
                        L1, L2 = d[v1][0], d[v1][1]
                    elif d[v1][0] == L1 and d[v1][1] < L2:
                        L1, L2 = d[v1][0], d[v1][1]

        if L1 == n + 1:
            print(-1, -1)
        else:
            print(L1 + 1, L2 + 1)












if __name__ == '__main__':
    for _ in range(int(input())):
        solve()
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

总结

对于mod 3和mod 9意义下的大数计算，或者字符串转大数
可以考虑转成数位和进行优化