QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #587501 | #6966. 排序问题 | _TLEer_ | 10 | 627ms | 35292kb | C++14 | 2.0kb | 2024-09-24 20:19:26 | 2024-09-24 20:19:28 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define MOD 998244353
int jc[500010],T,n,m,l,r,A,x[200010],p,q;
int adeld,deld,H,adm,h0,ny,inv[1000010],invj[1000010],mxs[200010],cnt;
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,mp2;
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<=1000000;i++){
if(i<=500000)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;
assert(i>500000||(jc[i]*invj[i]%MOD)==1);
}
cin>>T;
while(T--){
mp.clear();mp2.clear();
cnt=0;H=-1;
cin>>n>>m>>l>>r;
A=jc[n+m];
for(int i=1;i<=n;i++){
cin>>x[i];deld=r-l+1;
if(l<=x[i]&&x[i]<=r)
mp2[x[i]]++;
else mp[x[i]]++;
}
for(auto x:mp2)
mxs[cnt++]=x.second;
deld-=cnt;
// cout<<cnt<<' '<<deld<<'\n';
sort(mxs,mxs+cnt);
mxs[cnt]=-1;mxs[cnt+1]=0;
for(h0=0;h0<cnt;){
adm=0;adeld=0;
do
adm+=mxs[h0],adeld++,h0++;
while(mxs[h0+1]==mxs[h0]);
if(adm+m>=mxs[h0-1]*(adeld+deld))H=h0,m+=adm,deld+=adeld;
}
for(h0=H+1;h0<cnt;h0++)
mp[l+h0-H]=mxs[h0];
// if(deld>r-l+1)deld=r-l+1;
// cout<<A<<' '<<m<<' '<<deld<<'\n';
p=m/deld;
q=m%deld;
if(q&&(p+1)){
// cout<<"A";
// cout<<A<<'\n';
A=(A*ksm(invj[p+1],q))%MOD;
}
if((deld-q)&&(p)){
// cout<<"B";
// cout<<A<<'\n';
A=(A*ksm(invj[p],deld-q))%MOD;
}
// cout<<A<<'\n';
for(auto x:mp)
A=(A*invj[x.second])%MOD;
cout<<A<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 111ms
memory: 25516kb
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:
25200 32432400 283783500 100900800 756756000 831600 6652800 15120 17160 4054050
result:
ok 10 numbers
Test #2:
score: 0
Wrong Answer
time: 106ms
memory: 24676kb
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:
1995840 5040 194594400 9979200 75675600 100900800 3780 3326400 33264 22680
result:
wrong answer 3rd numbers differ - expected: '32432400', found: '194594400'
Test #3:
score: 0
Wrong Answer
time: 111ms
memory: 26184kb
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:
120120 907200 83160 252252000 25200 75600 2494800 1120 1081080 226800
result:
wrong answer 2nd numbers differ - expected: '453600', found: '907200'
Test #4:
score: 0
Wrong Answer
time: 113ms
memory: 24860kb
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:
636052443 222496631 147239592 784272834 106703011 308671587 930684219 993816426 951947415 469395048 795255157 40695617 733872422 688686243 290981945 962470247 616073681 572565308 203641067 886682628 929633604 236810426 497935370 639669234 379189382 573590458 870830749 908424510 145496374 286368636 9...
result:
wrong answer 1st numbers differ - expected: '817148398', found: '636052443'
Test #5:
score: 0
Wrong Answer
time: 113ms
memory: 24764kb
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:
218733857 683553113 546443689 192411465 177414523 123123992 182591455 394092994 801484762 987277151 946289139 826930864 600158503 650936985 624308302 914837519 52369352 452775136 626451618 361423520 264247840 354696853 708976628 867487992 423162123 448991260 940509905 212754645 48561576 170222075 44...
result:
wrong answer 1st numbers differ - expected: '608489105', found: '218733857'
Test #6:
score: 0
Wrong Answer
time: 154ms
memory: 33916kb
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:
434108025 549302632 394302733 421678599 90720 29937600 184800 95040 113513400 554400 378378000 138600 75600 25200 454053600 181440 907200 9979200 110880 2520 50400 50400 1441440 547558588 821337882 29937600 1120 415800 454053600 129163764 7920 831600 90720 277200 138600 277200 100900800 14414400 144...
result:
wrong answer 2nd numbers differ - expected: '686210610', found: '549302632'
Test #7:
score: 0
Wrong Answer
time: 153ms
memory: 32088kb
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:
868451621 503856708 502941036 201761277 3628800 75600 21527294 55440 9979200 554400 315591831 9979200 19958400 39916800 10080 504504000 119750400 9459450 100900800 277200 5040 907200 50400 362880 3603600 239500800 39916800 19958400 4989600 4989600 479001600 19958400 45360 831441387 2494800 558510847...
result:
wrong answer 2nd numbers differ - expected: '486359522', found: '503856708'
Test #8:
score: 0
Wrong Answer
time: 627ms
memory: 35292kb
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:
101621976 593687525 83871083 478145514 792423742 706387781 593979031 111652897 41325256 260211701 414637790 665849438 913397652 980765230 254699744 488014740 295550767 256256548 424789214 1247400 279173343 4804800 492688569 263232904 728513423 687990592 75675600 511331093 435245378 321873426 1995840...
result:
wrong answer 1st numbers differ - expected: '400144591', found: '101621976'
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:
625190976
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...
output:
434511896