UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213581#2770. 子序列erican803463ms6884kbC++112.3kb2024-11-12 21:14:372024-11-12 23:46:24

answer

// Problem: D. 子序列
// Contest: undefined - NOIP2024训练赛 03
// URL: http://noi.ac/contest/1155/problem/2770
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
// 
#include<bits/stdc++.h>

using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long 
#define pb push_back
#define itn int
#define ps second 
#define pf first


#define rd read()
int read(){
  int xx = 0, ff = 1;char ch = getchar();
  while (ch < '0' || ch > '9'){
    if (ch == '-')ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
  return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {cerr << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
	for (auto v: a) cerr << v << ' ';err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
	cerr << a << ' ';err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e5+5;
const ull P=137;
const int INF=1e18+7;
const int MOD=998244353;
/*

策略


*/	


int n,m;
int a[N];

namespace SGT{
	
	struct Node{
		int a[22];
		
		void init(){
			memset(a,0,sizeof a);
		}
	}t[N<<2];//区间内和%m=j的序列个数
	
	Node merge(Node a,Node b){
		Node c;
		c.init();
		for(int i=0;i<m;i++){
			for(int j=0;j<m;j++){
				c.a[(i+j)%m]+=a.a[j]*b.a[i]%MOD;
				if(c.a[(i+j)%m]>MOD)c.a[(i+j)%m]-=MOD;
				
			}
			c.a[i]+=(a.a[i]+b.a[i])%MOD;
			if(c.a[i]>MOD)c.a[i]-=MOD;
		}
		return c;
	}
	
	void build(int x,int l,int r){
		if(l==r){
			t[x].a[a[l]%m]++;
			return ;
		}
		
		int mid=l+r>>1;
		build(x<<1,l,mid);
		build(x<<1|1,mid+1,r);
		
		t[x]=merge(t[x<<1],t[x<<1|1]);
		
	}
	
	Node query(int x,int l,int r,int pl,int pr){
		if(pl<=l&&pr>=r)return t[x];
		int mid=l+r>>1;
		int fl=0,fr=0;
		Node nl,nr;
		if(pl<=mid)fl=1,nl=query(x<<1,l,mid,pl,pr);
		if(pr>mid)fr=1,nr=query(x<<1|1,mid+1,r,pl,pr);
		if(fl+fr==1){
			if(fl)return nl;
			return nr;
		}
		return merge(nl,nr);
	}
}using namespace SGT;

signed main(){
	 n=rd,m=rd;
	for(int i=1;i<=n;i++){
		a[i]=rd;
	}
	
	
	build(1,1,n);
	
	// cdbg("OK");
	int q=rd;
	while(q--){
		int a=rd,b=rd;
		cout<<query(1,1,n,a,b).a[0]+1<<'\n';
	}
	
	
}


详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 4
Accepted
time: 0ms
memory: 1176kb

input:

10 20
7 5 5 1 7 13 19 10 2 7
10
10 10
6 7
6 8
4 10
8 9
5 8
6 10
5 5
2 6
6 8

output:

1
1
1
9
1
2
2
1
2
1

result:

ok 10 lines

Test #2:

score: 4
Accepted
time: 0ms
memory: 1176kb

input:

10 20
15 0 15 10 6 18 1 13 3 1
10
1 2
4 9
3 7
4 8
6 10
2 3
1 4
2 5
2 9
5 9

output:

2
4
2
2
2
2
4
2
12
3

result:

ok 10 lines

Test #3:

score: 4
Accepted
time: 0ms
memory: 1176kb

input:

10 20
8 9 17 13 10 13 16 11 19 3
10
6 9
3 9
2 6
1 10
5 10
6 10
4 5
2 4
10 10
3 5

output:

2
9
3
56
4
2
1
1
1
2

result:

ok 10 lines

Test #4:

score: 4
Accepted
time: 0ms
memory: 1176kb

input:

10 20
12 8 11 1 0 3 2 3 19 17
10
5 7
1 3
1 10
2 6
4 10
5 9
5 9
3 10
4 8
4 8

output:

2
2
52
4
14
2
2
16
2
2

result:

ok 10 lines

Test #5:

score: 4
Accepted
time: 0ms
memory: 1176kb

input:

10 20
7 0 2 2 8 12 10 7 1 2
10
9 9
6 9
3 7
3 8
1 6
2 4
6 8
4 5
1 6
8 9

output:

1
2
4
4
4
2
1
1
4
1

result:

ok 10 lines

Test #6:

score: 4
Accepted
time: 3ms
memory: 1216kb

input:

100 20
3 15 11 17 7 9 16 11 6 0 1 1 19 15 18 0 14 12 17 9 19 12 18 9 4 14 11 5 18 10 4 18 14 8 14 8 ...

output:

2
3
52430
2
6597996
1677704
639171407
499955182
107374112
3299510
620272825
104768
1639
719742463
84...

result:

ok 100 lines

Test #7:

score: 4
Accepted
time: 3ms
memory: 1220kb

input:

100 20
3 7 17 4 9 6 6 15 18 1 3 5 19 13 2 7 9 10 4 5 0 10 18 18 6 0 1 15 16 12 2 7 6 0 17 2 14 18 4 ...

output:

3355488
198
146407370
410865364
493515490
6710976
7
106
8
1677728
6
551274971
1
252524913
909485871
...

result:

ok 100 lines

Test #8:

score: 4
Accepted
time: 3ms
memory: 1212kb

input:

100 20
1 11 5 10 8 2 11 14 2 11 7 4 13 4 2 1 13 4 0 13 4 8 3 12 12 17 12 13 16 2 5 12 13 0 5 11 0 7 ...

output:

26391984
10
102265781
102298549
692699452
409
5
214748032
1677728
535722995
535730163
848
2
3299254
...

result:

ok 100 lines

Test #9:

score: 4
Accepted
time: 3ms
memory: 1220kb

input:

100 20
8 18 4 8 11 9 1 19 7 14 7 13 4 3 14 0 10 3 13 16 2 5 17 18 7 10 7 3 19 1 16 18 7 13 19 13 2 1...

output:

804
29
26228
214748368
26
406
144284306
107374200
3276
214748736
13196104
102
209724
3355344
419461
...

result:

ok 100 lines

Test #10:

score: 4
Accepted
time: 3ms
memory: 1212kb

input:

100 20
17 1 13 11 0 8 12 2 4 15 14 18 6 6 5 16 18 4 6 19 4 0 4 6 10 19 5 4 18 17 14 16 3 0 1 6 2 4 0...

output:

107223667
107374192
766721907
52
3355432
882475258
396
13195992
1
312054174
156027151
8
640072527
44...

result:

ok 100 lines

Test #11:

score: 4
Accepted
time: 43ms
memory: 1528kb

input:

1000 20
7 14 19 15 16 8 19 15 5 5 6 3 4 16 0 1 7 6 14 3 12 2 4 5 16 12 12 8 1 9 6 13 4 10 12 16 11 7...

output:

339309012
715944960
16970373
501317746
497971938
785900425
283406068
695993316
288567892
854664381
7...

result:

ok 1000 lines

Test #12:

score: 4
Accepted
time: 45ms
memory: 1532kb

input:

1000 20
16 7 12 15 13 10 8 1 14 16 13 6 16 7 4 11 0 17 6 3 4 8 17 10 3 11 18 13 17 19 15 4 7 17 12 4...

output:

12
484141516
418898843
384084964
178290006
933245386
52381
892337346
229891253
934700126
807539512
7...

result:

ok 1000 lines

Test #13:

score: 4
Accepted
time: 40ms
memory: 1532kb

input:

1000 20
7 7 16 0 12 6 11 3 7 16 12 11 1 7 17 0 11 8 14 17 8 17 7 18 1 11 14 0 6 5 10 0 12 15 1 4 5 1...

output:

425631668
766990330
470949041
144283538
76394829
244140496
139661591
660069093
200874398
25390655
76...

result:

ok 1000 lines

Test #14:

score: 4
Accepted
time: 45ms
memory: 1528kb

input:

1000 20
19 3 14 11 9 17 18 4 11 5 0 18 2 11 13 12 8 10 15 19 12 9 2 15 5 19 14 17 17 7 18 5 2 8 5 0 ...

output:

778881096
21365162
250529076
897109757
514479914
7228728
941349307
893048929
815002080
383473661
308...

result:

ok 1000 lines

Test #15:

score: 4
Accepted
time: 44ms
memory: 1528kb

input:

1000 20
16 19 4 2 2 19 19 5 11 4 16 7 17 6 11 11 7 10 6 3 15 1 11 12 5 11 12 13 3 10 12 2 19 9 4 8 6...

output:

137484337
590803498
174472747
415795727
331378054
86892911
572721242
751509743
544015630
579988222
5...

result:

ok 1000 lines

Test #16:

score: 4
Accepted
time: 634ms
memory: 6884kb

input:

10000 20
12 8 12 19 9 19 1 10 19 11 12 10 19 5 0 16 17 1 9 18 18 13 6 0 14 16 6 6 3 6 17 2 13 19 13 ...

output:

874193350
88092426
703854077
255513247
263525020
961914369
501713148
112245351
4751861
552142943
766...

result:

ok 10000 lines

Test #17:

score: 4
Accepted
time: 649ms
memory: 6884kb

input:

10000 20
8 15 6 17 5 13 11 1 7 9 16 16 15 12 4 19 18 2 3 10 13 15 12 5 3 6 15 2 0 11 8 19 13 18 12 1...

output:

11498054
218890270
805811648
523169045
36644268
676722590
107529713
389206944
180310864
370902170
93...

result:

ok 10000 lines

Test #18:

score: 4
Accepted
time: 646ms
memory: 6880kb

input:

10000 20
0 9 6 6 17 19 11 13 18 14 0 10 3 0 0 11 12 11 2 19 18 12 13 16 8 7 14 12 10 2 7 3 4 18 10 1...

output:

963045808
67765534
341654959
274135849
984343299
760669853
518406338
929293037
928480977
282120869
5...

result:

ok 10000 lines

Test #19:

score: 4
Accepted
time: 648ms
memory: 6880kb

input:

10000 20
5 13 8 2 2 13 16 17 9 8 15 10 1 12 2 18 19 1 0 17 9 7 16 14 0 9 19 14 13 3 19 17 5 3 19 17 ...

output:

875247851
468456670
916495575
626409154
397961025
981686654
910510358
489047816
475311520
621799641
...

result:

ok 10000 lines

Test #20:

score: 4
Accepted
time: 654ms
memory: 6884kb

input:

10000 20
5 8 19 15 4 8 12 14 4 5 16 13 17 9 3 3 15 4 15 19 17 8 14 16 16 13 19 18 19 7 13 5 11 11 12...

output:

48
749885568
651004611
360760522
382504567
80840770
984919888
975485976
602298974
810921063
70525290...

result:

ok 10000 lines

Test #21:

score: 0
Time Limit Exceeded

input:

200000 20
11 5 3 3 2 9 10 10 15 4 19 1 3 0 19 19 15 0 0 12 14 16 1 8 3 18 10 6 14 11 2 7 17 2 0 1 12...

output:

57545307
511527331
937554911
981484815
371783591
343612155
144012387
671312765
172565790
646720741
6...

result:


Test #22:

score: 0
Time Limit Exceeded

input:

200000 20
13 15 5 3 2 0 3 4 6 16 14 0 4 11 8 10 18 5 3 12 1 7 2 16 13 19 16 16 3 16 6 8 2 6 10 0 13 ...

output:

110393808
614595997
675993626
352172325
656690898
85268545
562486581
625807444
256144882
715123322
1...

result:


Test #23:

score: 0
Time Limit Exceeded

input:

200000 20
15 8 8 12 19 10 4 14 16 6 3 17 13 4 14 17 5 15 19 4 0 3 17 5 4 9 14 19 10 11 9 13 0 3 18 0...

output:

218640057
773256405
471300811
440220680
22914143
995240220
74748924
961518981
576143084
505721968
98...

result:


Test #24:

score: 0
Time Limit Exceeded

input:

200000 20
11 4 7 18 16 15 15 18 11 2 4 1 17 18 6 9 19 12 2 14 8 6 10 4 15 16 17 13 18 1 15 18 15 9 1...

output:

438860874
296640640
148674750
179598802
959408351
495193666
256751307
388747462
742085106
275253591
...

result:


Test #25:

score: 0
Time Limit Exceeded

input:

200000 20
5 3 18 11 17 13 14 19 0 0 1 3 4 13 8 1 15 7 15 2 12 8 3 15 8 1 4 8 7 5 9 16 9 16 0 14 2 16...

output:

739309565
623604720
856984772
733601935
300585886
799383531
11214289
118961089
279592831
299606639
5...

result: