codeforces：F.KireiandtheLinearFunction【暴力优化+避开大数运算+避开str切片转int】

分析

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

优化点

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

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

Ac code

import sys
from collections import defaultdict
from itertools import accumulate
input &＃61; sys.stdin.readlinedef solve():s &＃61; input().strip()n &＃61; len(s)w, m &＃61; list(map(int, input().split()))d &＃61; defaultdict(list)# ---------------------------# slide window# big number operation: bad!# ---------------------------# curr &＃61; 0# for i in range(n):# if i # curr &＃61; curr * 10 &＃43; int(s[i])# else:# d[curr % 9].append(i - w)# curr -&＃61; int(s[i - w]) * 10 ** (w - 1)# curr &＃61; curr * 10 &＃43; int(s[i])# d[curr % 9].append(n - w)# %3 or %9 the same as the sum of the digitslst &＃61; [int(c) for c in s]preSum &＃61; list(accumulate(lst, initial &＃61; 0))# avoid big number, use sum of digitsfor i in range(n - w &＃43; 1):u &＃61; (preSum[i &＃43; w] - preSum[i]) % 9d[u].append(i)#print(d)for _ in range(m):l, r, k &＃61; list(map(int, input().split()))# ---------------------------# slice &＃43; int &＃61;> o(r - l &＃43; 1) &＃61;> bad as o(N)# ---------------------------# v_l_r &＃61; int(s[l - 1:r]) % 9# use preSum insteadv_l_r &＃61; (preSum[r] - preSum[l - 1]) % 9# v2 &＃61; ki - v1 * v_l_rL1, L2 &＃61; n &＃43; 1, n &＃43; 1for v1 in range(9):if len(d[v1]) > 0:v2 &＃61; (k - v1 * v_l_r) % 9if v1 !&＃61; v2 and len(d[v2]) > 0:# choices.append([d[v1][0], d[v2][0]])if d[v1][0] < L1:L1, L2 &＃61; d[v1][0], d[v2][0]elif d[v1][0] &＃61;&＃61; L1 and d[v2][0] < L2:L1, L2 &＃61; d[v1][0], d[v2][0]elif v1 &＃61;&＃61; v2 and len(d[v1]) > 1:# choices.append([d[v1][0], d[v1][1]])if d[v1][0] < L1:L1, L2 &＃61; d[v1][0], d[v1][1]elif d[v1][0] &＃61;&＃61; L1 and d[v1][1] < L2:L1, L2 &＃61; d[v1][0], d[v1][1]if L1 &＃61;&＃61; n &＃43; 1:print(-1, -1)else:print(L1 &＃43; 1, L2 &＃43; 1)if __name__ &＃61;&＃61; &＃39;__main__&＃39;:for _ in range(int(input())):solve()


总结

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