QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#587266	#6966. 排序问题	_TLEer_	30	368ms	23104kb	C++14	1.3kb	2024-09-24 18:59:03	2024-09-24 18:59:03

Judging History

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

[2024-09-24 18:59:03]
评测

测评结果：30
用时：368ms
内存：23104kb

查看

[2024-09-24 18:59:03]
提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define MOD 998244353
int jc[2000010],T,n,m,l,r,A,x[2000010],p,q,ny,inv[2000010],invj[2000010];
int ksm(int p,int q=MOD-2){
    int ans=1;
    while(q){
        if(q&1){ans=ans*p%MOD;}
        p=p*p%MOD;
        q>>=1;
    }
    return ans;
}
map<int,int> mp;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();cout.tie();
    jc[0]=invj[0]=jc[1]=invj[1]=inv[1]=inv[0]=1;
    for(int i=2;i<=200000;i++){
        jc[i]=(jc[i-1]*i)%MOD;
        inv[i]=ksm(i);
        // if(inv[i])cout<<i<<' '<<ksm(i)<<'\n';
        invj[i]=(invj[i-1]*inv[i])%MOD;
    }
    cin>>T;
    while(T--){
        mp.clear();
        cin>>n>>m>>l>>r;
        A=jc[n+m];
        for(int i=1;i<=n;i++){
            cin>>x[i];
            if(l<=x[i]&&x[i]<=r)
                m++;
            else mp[x[i]]++;
        }
        p=m/(r-l+1);
        q=m%(r-l+1);
        if(q&&(p+1)){
            // cout<<"A";
            // cout<<A<<'\n';
            A=(A*ksm(invj[p+1],q))%MOD;
        }
        if((r-q-l+1)&&(p)){
            // cout<<"B";
            // cout<<A<<'\n';
            A=(A*ksm(invj[p],r-q-l+1))%MOD;
        }
        // cout<<A<<'\n';
        for(auto x:mp)
            A=(A*invj[x.second])%MOD;
        cout<<A<<'\n';
    }
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests

Final Tests

Test #1:

score: 10

Accepted

time: 16ms

memory: 15476kb

input:

10
5 5 7 8
1 8 5 1 5
8 5 4 7
8 8 2 5 2 6 6 2
8 7 3 4
6 5 8 4 5 1 6 1
8 6 7 8
6 5 6 2 3 6 1 8
7 8 4 7
2 7 3 2 3 6 6
7 4 6 7
1 4 1 4 3 7 2
6 6 3 5
4 1 8 2 5 7
5 4 5 5
8 6 7 3 2
5 8 6 6
6 7 3 2 1
7 8 3 3
2 7 5 6 2 7 6

output:

result:

ok 10 numbers

Test #2:

score: 10

Accepted

time: 21ms

memory: 14968kb

input:

10
8 4 4 4
8 2 5 6 6 3 4 7
5 4 3 4
2 3 2 3 5
7 6 4 8
8 8 4 8 2 2 7
6 6 4 8
1 1 1 6 3 4
6 8 5 6
4 1 4 3 7 8
7 7 3 6
3 7 4 7 4 2 3
5 4 6 6
3 1 1 5 5
8 4 7 8
7 6 2 5 5 7 3 2
5 7 3 4
4 2 4 4 8
4 5 3 6
5 3 6 1

output:

result:

ok 10 numbers

Test #3:

score: 10

Accepted

time: 21ms

memory: 15948kb

input:

10
6 8 6 6
7 4 6 2 7 8
6 4 3 7
7 1 7 4 5 8
6 6 3 4
3 2 4 8 3 8
7 8 4 7
3 4 2 5 5 6 4
6 4 6 8
7 6 4 8 4 7
5 5 6 8
5 3 3 6 7
6 5 3 6
7 2 1 4 6 7
4 4 6 7
5 1 6 6
8 5 8 8
1 5 4 3 1 5 8 4
6 4 3 6
4 4 2 6 3 1

output:

result:

ok 10 numbers

Test #4:

score: 0

Wrong Answer

time: 26ms

memory: 15368kb

input:

300
252 260 70 255
7 267 105 21 192 111 287 290 88 97 39 182 76 36 8 271 138 213 16 36 70 119 8 201 278 84 152 225 226 140 265 90 31 264 206 105 82 18 160 192 10 181 66 91 142 138 174 12 66 108 135 235 160 218 93 280 187 190 115 16 205 109 103 5 35 136 36 72 158 217 240 19 161 32 191 163 170 228 30 ...

output:

result:

wrong answer 1st numbers differ - expected: '817148398', found: '898128067'

Test #5:

score: 0

Wrong Answer

time: 22ms

memory: 16296kb

input:

300
227 278 55 261
255 85 153 179 43 15 8 158 281 261 243 93 242 4 129 222 202 43 279 9 219 243 63 212 38 39 152 299 224 204 267 267 34 154 250 78 40 118 98 186 12 268 277 192 84 170 248 276 96 150 232 209 56 179 82 3 240 150 11 218 173 273 81 288 187 272 140 265 272 42 208 195 86 44 73 93 279 23 19...

output:

result:

wrong answer 1st numbers differ - expected: '608489105', found: '478570689'

Test #6:

score: 0

Wrong Answer

time: 55ms

memory: 19464kb

input:

1008
110000 200000 80799550 89322792
80846588 80840728 80846740 80846226 80837919 80808035 80811892 80821541 80828204 80835347 80833535 80821744 80805463 80848335 80818082 80835681 80807218 80807081 80838326 80821628 80803817 80845303 80840877 80843012 80830165 80826985 80810131 80822178 80809793 80...

output:

result:

wrong answer 1st numbers differ - expected: '434108025', found: '0'

Test #7:

score: 0

Wrong Answer

time: 49ms

memory: 19060kb

input:

1169
100000 200000 80463410 88931820
80468507 80491681 80487314 80485519 80482007 80466540 80470566 80507366 80467570 80479753 80513204 80504461 80496204 80464814 80481678 80471573 80508511 80507514 80500322 80491106 80467094 80488511 80482243 80488511 80501739 80476062 80470590 80501419 80506225 80...

output:

result:

wrong answer 1st numbers differ - expected: '868451621', found: '0'

Test #8:

score: 0

Wrong Answer

time: 368ms

memory: 23104kb

input:

16681
200000 200000 76883519 76941647
76887826 76896834 76928035 76920567 76922595 76911193 76908583 76895058 76907525 76899189 76891847 76898478 76901834 76895730 76925717 76885225 76930475 76932521 76925233 76911515 76931174 76884143 76913261 76928484 76897028 76926818 76931633 76893762 76891824 7...

output:

result:

wrong answer 1st numbers differ - expected: '400144591', found: '0'

Test #9:

score: 0

Runtime Error

input:

16652
200000 112 49071552 49072622
49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 49071552 4907...

output:

result:

Test #10:

score: 0

Runtime Error

input:

16731
200000 104 5062478 5063630
5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 5062478 506...