QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#290187#4623. Matryoshka DollyspmAC ✓184ms199160kbC++201.6kb2023-12-24 15:27:452023-12-24 15:27:45

Judging History

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

  • [2023-12-24 15:27:45]
  • 评测
  • 测评结果:AC
  • 用时:184ms
  • 内存:199160kb
  • [2023-12-24 15:27:45]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
template<typename T>inline void ckmax(T &x,T y){x=x<y?y:x;}
template<typename T>inline void ckmin(T &x,T y){x=x>y?y:x;}
template<typename T=int>inline T read(){
    T res=0,f=1; char k;
    while(!isdigit(k=getchar())) if(k=='-') f=-1;
    while(isdigit(k)) res=res*10+k-'0',k=getchar();
    return res*f;
}
template<typename T>inline void print(T x,bool fl=1){
    if(x<0) putchar('-'),x=-x; 
    if(x>=10) print(x/10,0);
    putchar(x%10+'0');
    if(fl) putchar('\n');
}
const int mod=998244353;
inline int add(int x,int y,int Mod=mod){return x+y>=Mod?x+y-Mod:x+y;}
inline int del(int x,int y,int Mod=mod){return x-y<0?x-y+Mod:x-y;}
inline int mul(int x,int y,int Mod=mod){return x*y-x*y/Mod*Mod;}
inline void ckadd(int &x,int y,int Mod=mod){x=x+y>=Mod?x+y-Mod:x+y;}
inline void ckdel(int &x,int y,int Mod=mod){x=x-y<0?x-y+Mod:x-y;}
inline void ckmul(int &x,int y,int Mod=mod){x=x*y-x*y/Mod*Mod;}
inline int ksm(int x,int y,int Mod=mod){int res=1; for(;y;y>>=1,ckmul(x,x,Mod)) if(y&1) ckmul(res,x,Mod); return res;}
const int N=5010;
int n,k,r,a[N],dp[N][N],f[N];
signed main(){
    int T=read();
    while(T--){
        n=read(),k=read(),r=read();
        for(int i=1;i<=n;++i) a[i]=read();
        dp[0][0]=1;
        for(int i=1;i<=n;++i){
            f[i]=0;
            for(int j=1;j<i;++j) if(a[i]-a[j]<r) ++f[i];
            for(int j=1;j<=k;++j){
                dp[i][j]=add(dp[i-1][j-1],mul(dp[i-1][j],max(0ll,j-f[i])));
            }
        }
        print(dp[n][k]);
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 184ms
memory: 199160kb

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