QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#64743 | #4623. Matryoshka Doll | qinjianbin# | AC ✓ | 177ms | 199264kb | C++17 | 777b | 2022-11-25 14:36:22 | 2022-11-25 14:38:09 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
const int N = 5000 + 10;
const int mod = 998244353;
int L[N], a[N], n, k, R;
ll dp[N][N];
int main()
{
int T; scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &n, &k, &R);
_for(i, 1, n) scanf("%d", &a[i]);
int l = n;
for(int r = n; r >= 1; r--)
{
while(l - 1 >= 0 && a[r] - a[l] < R) l--;
L[r] = l;
}
dp[0][0] = 1;
_for(i, 1, n)
_for(j, 1, k)
{
dp[i][j] = dp[i - 1][j - 1];
int t = i - L[i] - 1;
if(j - t > 0) dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j - t) % mod) % mod;
}
printf("%lld\n", dp[n][k]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 177ms
memory: 199264kb
input:
20 4 3 2 1 2 3 4 4 2 1 1 1 2 2 10 3 5 7 20 27 27 34 36 40 56 63 98 10 5 10 5 6 11 20 34 39 42 57 86 99 100 2 4 61 139 210 338 426 591 614 637 658 678 699 1002 1015 1162 1424 1433 1502 1756 1994 2073 2164 2189 2258 2305 2460 2464 2497 2507 2512 2526 2557 2742 2794 2809 3060 3075 3201 3226 3380 3576 3...
output:
3 2 2852 10554 719747106 690165012 206258543 359242369 612315029 205154325 247697612 404757277 1 927604200 0 366237347 948502315 1 119095265 1
result:
ok 20 lines