NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #213568 | #2770. 子序列 | one_zero_four_zero | 60 | 908ms | 2900kb | C++11 | 1.7kb | 2024-11-12 20:56:16 | 2024-11-12 23:39:06 |
answer
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define mod 998244353LL
using namespace std;
int N, Q, M;
int l, r;
int A[200005];
int cnt[200005][22];
int p[200005], inv[200005];
int C[21][21][200005];
int qpow(int a, int b){
int res = 1;
while (b){
if (b & 1) res = (1LL * res * a) % mod;
a = (1LL * a * a) % mod;
b >>= 1;
}
return res;
}
void __init(){
p[0] = inv[0] = 1;
for (int i = 1; i <= 200000; i ++){
p[i] = (1LL * i * p[i - 1]) % mod;
inv[i] = qpow(p[i], mod - 2);
}
}
long long getC(int n, int m){
if (n < m) return 0LL;
long long res = p[n];
res = (res * inv[n - m]) % mod;
res = (res * inv[m]) % mod;
return res;
}
long long calc(int l, int r){
long long res = 0;
vector<int> num(22);
long long dp[22][22] = {0};
for (int i = 0; i < M; i ++){
num[i] = cnt[r][i] - cnt[l - 1][i];
// cout << i << " " << num[i] << ";;\n";
}
dp[0][0] = 1LL;
for (int i = 0; i < M; i ++){ // kao lv i_th
for (int val = 0; val < M; val ++){
// cout << i << " " << val << " " << dp[i][val] << ";;\n";
int cur = 0;
for (int j = 0; j <= num[i]; j ++){
dp[i + 1][(val + cur) % M] += (dp[i][val] * getC(num[i], j)) % mod;
dp[i + 1][(val + cur) % M] %= mod;
cur = (cur + i) % M;
}
}
}
return dp[M][0];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("../data.in", "r", stdin);
freopen("../data.out", "w", stdout);
#endif
scanf("%d %d", &N, &M);
for (int i = 1; i <= N; i ++){
scanf("%d", &A[i]);
for (int j = 0; j < M; j ++){
cnt[i][j] = cnt[i - 1][j];
}
cnt[i][A[i]] ++;
}
__init();
scanf("%d", &Q);
while (Q --){
scanf("%d %d", &l, &r);
printf("%lld\n", calc(l, r) % mod);
}
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 4
Accepted
time: 25ms
memory: 2804kb
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: 32ms
memory: 2804kb
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: 29ms
memory: 2800kb
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: 33ms
memory: 2800kb
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: 32ms
memory: 2804kb
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: 34ms
memory: 2808kb
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: 32ms
memory: 2816kb
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: 32ms
memory: 2812kb
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: 34ms
memory: 2816kb
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: 34ms
memory: 2812kb
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: 119ms
memory: 2900kb
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: 115ms
memory: 2896kb
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: 124ms
memory: 2896kb
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: 121ms
memory: 2896kb
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: 112ms
memory: 2892kb
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: 0
Time Limit Exceeded
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:
Test #17:
score: 0
Time Limit Exceeded
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:
Test #18:
score: 0
Time Limit Exceeded
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:
Test #19:
score: 0
Time Limit Exceeded
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:
Test #20:
score: 0
Time Limit Exceeded
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:
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:
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:
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:
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:
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...
