QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#587295	#6966. 排序问题	_TLEer_	30	484ms	30924kb	C++14	1.3kb	2024-09-24 19:12:50	2024-09-24 19:12:51

Judging History

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

[2024-09-24 19:12:51]
评测

测评结果：30
用时：484ms
内存：30924kb

查看

[2024-09-24 19:12:50]
提交

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,ny,inv[1000010],invj[1000010];
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<=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;
    }
    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;
}

源文件, 语言: C++14

詳細信息

Pretests

Final Tests

Test #1:

score: 10

Accepted

time: 105ms

memory: 24740kb

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: 113ms

memory: 24728kb

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: 105ms

memory: 24640kb

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: 111ms

memory: 24812kb

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: 103ms

memory: 24736kb

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: 130ms

memory: 28076kb

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: '35932350'

Test #7:

score: 0

Wrong Answer

time: 137ms

memory: 27828kb

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: '46306511'

Test #8:

score: 0

Wrong Answer

time: 484ms

memory: 30924kb

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: '779010570'

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:

662301616

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:

217615273