QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#227469#7400. Digital RootCrysflyTL 10ms13736kbC++173.2kb2023-10-27 16:22:182023-10-27 16:22:18

Judging History

你现在查看的是最新测评结果

  • [2023-10-27 16:22:18]
  • 评测
  • 测评结果:TL
  • 用时:10ms
  • 内存:13736kb
  • [2023-10-27 16:22:18]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
 
#define maxn 200005
#define inf 0x3f3f3f3f

int toint(char c){
	if(isdigit(c))return c&15;
	return c-'a'+10;
}

int n,m,k;
char s[maxn];
int a[maxn],aa[maxn],sum[maxn][17];

int pre[17],id[17];
pii tmp[17];

int ask(int x,int l,int r){
	int res=sum[r][x];
	if(l>0)res-=sum[l-1][x];
	return res;
}

int f[17][1<<17];
void fwt(int*f,int k){
	For(i,0,k-1)
		For(j,0,(1<<k)-1)
			if(j>>i&1) f[j]+=f[j^(1<<i)];
}

int res0,res1[19],res10[19];

signed main()
{
	n=read(),m=read(),k=read(),cin>>(s+1);
	sum[0][0]=1;
	For(i,1,n){
		a[i]=a[i-1]+toint(s[i]),a[i]%=(k-1);
		aa[i]=aa[i-1]+(toint(s[i])!=0);
		res10[toint(s[i])]++;
		For(j,0,k-2)sum[i][j]=sum[i-1][j]+(j==a[i]);
	}
	memset(pre,-1,sizeof pre);
	For(j,0,k) id[j]=j;
	
	For(i,1,n){
		pre[toint(s[i])%(k-1)]=i;
		sort(id,id+k-1,[&](int x,int y){
			return pre[x]>pre[y];
		});
		int S=0;
		For(j,0,k-2){
			int r=pre[id[j]];
			int l=pre[id[j+1]]+1;
			l=max(l,1ll);
			S|=(1<<id[j]);
			if(l>r)continue;
		//	cout<<"i,l,r, "<<i<<" "<<l<<" "<<r<<" "<<S<<"\n";
			For(x,0,k-2)
				f[(a[i]-x+k-1)%(k-1)][S]+=ask(x,l-1,r-1);
		}
	}
	
	For(i,1,n)For(j,i,n){
		int S=0,T=0;
		For(p,i,j)S|=(1<<(toint(s[p])%(k-1))),T|=(1<<toint(s[p]));
	//	cout<<(a[j]-a[i-1]+k-1)%(k-1)<<" "<<S<<"\n";
		if(aa[j]-aa[i-1]<=1){
			if(aa[j]-aa[i-1]==0) ++res0;
			else {
				int x=0;
				For(_,1,k-1) if(T>>_&1) x=_;
				res1[x]++;
			}
		}
	}
	
	For(x,0,k-2) fwt(f[x],k-1);
	For(_,1,m){
		int y=read();
		string str; cin>>str;
		int S=0;
		for(auto c:str){
			int o=toint(c);
			S|=(1<<(o%(k-1)));
		}
		int res=n*(n+1)/2;
		For(x,0,k-2)if(x!=y%(k-1)){
			// if have j,x-i+j==y
			// j==y+i-x
			int T=0;
			For(i,0,k-2){
		//		cout<<(((y+i-x+k-1)%(k-1)))<<"\n";
				if(!(S>>((y+i-x+k-1)%(k-1))&1)) T|=(1<<i);
			}
		//	cout<<"x,T "<<x<<' '<<T<<" "<<f[x][T]<<"\n";
			res-=f[x][T];
		}
		if(y==0||y==k-1){
			if(y==0){
				res=res0;
				bool fl0=0;
				for(auto c:str) if(toint(c)==0) fl0=1;
				if(fl0){
					For(j,1,k-1) res+=res1[j];
				}
			}else{
			//	cout<<"ans "<<res<<"\n";
				bool fl=0,fl0=0;
				for(auto c:str){
					if(toint(c)==k-1)fl=1;
					if(toint(c)==0)fl0=1;
				}
				if(!fl){
					res-=res0;
				//	cout<<"QWQ "<<res<<"\n";
					if(fl0){
						For(j,1,k-2) {
							int s1=res10[j];
							int s2=res1[j]-s1;
							res-=s1;
							if(!(S>>(k-1-j)&1)) res-=s2;
						}
					}
				}
			}
		}
		cout<<res<<"\n";
	}
    return 0;
}
/*
5 10 5
01234
0 1

01234

*/

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 13736kb

input:

9 2 10
123456789
9 12
8 123456789

output:

24
45

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 1ms
memory: 7520kb

input:

5 10 5
01234
0 1
1 1
2 1
3 1
4 1
0 1
1 0
2 0
3 0
4 0

output:

1
13
9
9
9
1
10
9
10
6

result:

ok 10 tokens

Test #3:

score: 0
Accepted
time: 1ms
memory: 5476kb

input:

19 6 2
0010111001010011111
0 0
0 1
0 01
1 0
1 1
1 01

output:

42
11
42
179
190
190

result:

ok 6 tokens

Test #4:

score: 0
Accepted
time: 1ms
memory: 7488kb

input:

13 21 3
1010011001002
0 0
0 1
0 10
0 2
0 20
0 21
0 012
1 0
1 1
1 01
1 2
1 20
1 12
1 021
2 0
2 1
2 01
2 2
2 02
2 12
2 102

output:

36
10
36
10
36
10
36
78
90
91
78
78
91
91
58
76
76
91
91
91
91

result:

ok 21 tokens

Test #5:

score: 0
Accepted
time: 2ms
memory: 7520kb

input:

15 60 4
313213200103021
0 0
0 1
0 01
0 2
0 20
0 21
0 021
0 3
0 30
0 31
0 103
0 23
0 032
0 321
0 0132
1 0
1 1
1 10
1 2
1 02
1 12
1 021
1 3
1 30
1 13
1 310
1 23
1 203
1 312
1 1302
2 0
2 1
2 01
2 2
2 02
2 21
2 120
2 3
2 03
2 13
2 031
2 32
2 320
2 213
2 0321
3 0
3 1
3 01
3 2
3 20
3 12
3 201
3 3
3 30
3 1...

output:

27
5
27
5
27
5
27
5
27
5
27
5
27
5
27
96
118
120
105
105
120
120
96
96
120
120
105
105
120
120
89
104
104
118
120
120
120
89
89
104
104
120
120
120
120
100
93
103
99
105
108
108
120
120
120
120
120
120
120
120

result:

ok 60 tokens

Test #6:

score: 0
Accepted
time: 0ms
memory: 7512kb

input:

14 155 5
03033201040331
0 0
0 1
0 10
0 2
0 20
0 21
0 210
0 3
0 03
0 13
0 130
0 23
0 302
0 312
0 3201
0 4
0 40
0 14
0 140
0 42
0 042
0 421
0 0421
0 43
0 043
0 341
0 0143
0 423
0 3240
0 2314
0 30214
1 0
1 1
1 01
1 2
1 20
1 12
1 012
1 3
1 30
1 13
1 103
1 32
1 203
1 213
1 1302
1 4
1 40
1 41
1 041
1 24
1...

output:

26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
68
91
97
84
88
104
105
72
81
102
103
90
90
105
105
68
68
97
97
88
88
105
105
81
81
103
103
90
90
105
105
66
75
82
95
104
104
105
75
82
88
89
102
105
105
105
66
66
82
82
104
104
105
105
82
82
89
89
105
105
105
105
79
79
86
...

result:

ok 155 tokens

Test #7:

score: 0
Accepted
time: 2ms
memory: 9572kb

input:

11 378 6
34155331452
0 0
0 1
0 10
0 2
0 20
0 21
0 201
0 3
0 03
0 13
0 301
0 32
0 203
0 231
0 2301
0 4
0 04
0 14
0 401
0 42
0 402
0 412
0 0214
0 34
0 340
0 143
0 1340
0 234
0 4032
0 1243
0 03412
0 5
0 50
0 51
0 051
0 25
0 520
0 512
0 2015
0 35
0 053
0 513
0 5301
0 352
0 5320
0 5123
0 51302
0 45
0 054...

output:

11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
44
54
65
50
52
65
66
42
52
60
66
55
55
66
66
41
52
60
65
53
54
65
66
49
55
63
66
56
56
66
66
44
44
65
65
52
52
66
66
52
52
66
66
55
55
66
66
5...

result:

ok 378 tokens

Test #8:

score: 0
Accepted
time: 0ms
memory: 9596kb

input:

10 889 7
2433333441
0 0
0 1
0 01
0 2
0 20
0 21
0 210
0 3
0 03
0 13
0 301
0 32
0 032
0 123
0 3201
0 4
0 40
0 41
0 104
0 24
0 240
0 412
0 4102
0 34
0 304
0 143
0 1340
0 342
0 4320
0 2134
0 43210
0 5
0 05
0 51
0 051
0 52
0 502
0 251
0 2510
0 35
0 530
0 315
0 3510
0 253
0 0532
0 3521
0 05231
0 54
0 504
...

output:

10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
...

result:

ok 889 tokens

Test #9:

score: 0
Accepted
time: 0ms
memory: 11584kb

input:

12 2040 8
512641272172
0 0
0 1
0 10
0 2
0 02
0 12
0 120
0 3
0 30
0 13
0 310
0 23
0 203
0 132
0 1203
0 4
0 04
0 41
0 140
0 42
0 042
0 421
0 4102
0 43
0 043
0 143
0 0341
0 342
0 3402
0 3142
0 23410
0 5
0 05
0 51
0 501
0 25
0 502
0 251
0 1502
0 35
0 035
0 153
0 1350
0 253
0 2350
0 3125
0 31205
0 45
0 4...

output:

12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
...

result:

ok 2040 tokens

Test #10:

score: 0
Accepted
time: 5ms
memory: 11624kb

input:

17 4599 9
05628257863606468
0 0
0 1
0 10
0 2
0 02
0 21
0 210
0 3
0 03
0 13
0 013
0 23
0 032
0 231
0 0321
0 4
0 40
0 14
0 401
0 24
0 402
0 421
0 0124
0 34
0 043
0 134
0 1403
0 243
0 2043
0 3241
0 32140
0 5
0 50
0 15
0 501
0 52
0 205
0 215
0 5210
0 35
0 350
0 153
0 0351
0 523
0 0235
0 2135
0 05321
0 5...

output:

20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
...

result:

ok 4599 tokens

Test #11:

score: 0
Accepted
time: 10ms
memory: 13720kb

input:

12 10230 10
544253693210
0 0
0 1
0 01
0 2
0 02
0 21
0 102
0 3
0 30
0 13
0 130
0 32
0 023
0 213
0 0132
0 4
0 40
0 14
0 410
0 24
0 402
0 214
0 2014
0 43
0 043
0 431
0 4130
0 234
0 3420
0 3124
0 10423
0 5
0 05
0 15
0 105
0 52
0 250
0 251
0 1520
0 53
0 305
0 531
0 5013
0 352
0 3205
0 3251
0 12305
0 45
0...

output:

13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
...

result:

ok 10230 tokens

Test #12:

score: -100
Time Limit Exceeded

input:

11 22517 11
88902812271
0 0
0 1
0 01
0 2
0 02
0 21
0 102
0 3
0 03
0 31
0 013
0 32
0 230
0 213
0 2310
0 4
0 40
0 14
0 014
0 42
0 042
0 241
0 1402
0 43
0 034
0 341
0 4031
0 432
0 3024
0 2413
0 13204
0 5
0 05
0 51
0 015
0 25
0 520
0 512
0 2051
0 53
0 035
0 351
0 0531
0 523
0 2305
0 5321
0 51302
0 45
0 ...

output:

13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
...

result: