F. Kirei and the Linear Function（思维 + 哈希 + 预处理）

F. Kirei and the Linear Function

思维 + 哈希 + 预处理

分析

观察到每组数据的w是确定的，所以我们可以先对s的每个长度为w的子串[l,l+w-1]都给切片一下；
把他们的值%9算出来，用map存相同值的切片的左端点的集合；

那么问题来了，怎么快速算出每一段切片的十进制下%9的值？？？
由于字符串全都是0~9，且是%9，所以非常的特殊；
比如：321 = (31010)%9 + (210)%9 + 1%9 = (311) + (21) + 1;
所以可以发现每个切片的值就是切片中每个字符的值之和%9；
所以这里我们就可以用一个前缀和来记录处理一下每一个切片，就能快速算出来了；

当然更一般的写法就是直接字符串hash就行了，套个板子就行

然后对于每个询问，要求(v(l1) * v + v(l2)) % 9 = k; 的最小l1，l2；
所以我们可以直接枚举v(l1) (0~8);
那么v(l2) = (k - (v(l1) * v % 9) + 9) % 9;
然后判断一下，更新最小下标就行

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
#include <random>
#include<bitset>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define dre(x) scanf("%lf",&x)
#define ddre(a,b) scanf("%lf %lf",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
//#define int long long
// #define double long double
// typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, int> PCI;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 2e5 + 7;
const int N = 5e5 + 7;
const int M = 5e5 + 7;
const int mod = 131;
const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

ll sum[maxn];   //前缀和处理切片

void solve()
{	
	string s;
	cin>>s;
	s = ' ' + s;
	
	//前缀和
	for(int i=1;i<s.size();i++) sum[i] = sum[i-1] + (s[i] - '0');
	
	int w,m;
	cin>>w>>m;
	
	//求切片
	map<int,vector<int>> mp;    //存不同切片值的左端点下标
	for(int i=1;i+w-1<s.size();i++)
	{
		int j = i + w - 1;
		
		int num = (sum[j] - sum[i-1]) % 9;
		mp[num].pb(i);
	}
	
	while(m--)
	{
		int l,r,k;
		cin>>l>>r>>k;
		
		int num = (sum[r] - sum[l-1]) % 9;  //v的值
		
// 		cout<
		
		int ans1 = inf;
		int ans2 = inf;
		for(int v1=0;v1<=8;v1++)	//枚举v1
		{
			if(mp[v1].size() == 0) continue;
			
			int v2 = (k - (v1 * num % 9) + 9) % 9;
			
			if(mp[v2].size() == 0) continue;    //当前v2的没有切片
			if(v1 == v2 && mp[v1].size() == 1) continue;    //l1 = l2，不满足
			
			if(v1 != v2)    //v1 v2值不相等，则都取最小的下标更新
			{
			    if(ans1 > mp[v1][0])
			    {
			        ans1 = mp[v1][0];
			        ans2 = mp[v2][0];
			    }
			    else if(ans1 == mp[v1][0] && ans2 > mp[v2][0])
			        ans2 = mp[v2][0];
			}
			else    //v1 v2值相等，一样的
			{
			    if(ans1 > mp[v1][0])
			    {
			        ans1 = mp[v1][0];
			        ans2 = mp[v1][1];
			    }
			    else if(ans1 == mp[v1][0] && ans2 > mp[v1][1])
			        ans2 = mp[v1][1];
			}
		}
		
		if(ans1 == inf || ans2 == inf) ans1 = -1, ans2 = -1;
		cout<<ans1<<' '<<ans2<<'\n';
	}
}

int main()
{
	IOS;
	
	int t;
	cin>>t;
//	t = 1;
	
	while(t--)
	{
		solve();
	}
	
	return 0;
}

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152