ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213581 | #2770. 子序列 | erican | 80 | 3463ms | 6884kb | C++11 | 2.3kb | 2024-11-12 21:14:37 | 2024-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...