ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213033 | #3823. 艾特扣德 | drdilyor | 40 | 764ms | 19316kb | C++11 | 1.3kb | 2024-11-03 12:52:31 | 2024-11-03 13:02:35 |
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
int n=0,f=1,ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
n=n*10+ch-'0';
ch=getchar();
}
return n*f;
}
int n,m;
int a[1000005];
int fac[1000005],ifac[1000005];
const int mod=998244353;
int qkp(int b,int p){
int r=1;
while(p){
if(p&1)(r*=b)%=mod;
p/=2;
(b*=b)%=mod;
}
return r;
}
int C(int n,int m){
if(n<m)return 0;
return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void solve(){
n=read(),m=read();
for(int i=1;i<=m;i++)a[i]=read();
bool h=0;
for(int i=1;i<=m;i++)h|=(a[i]<=1);
if(h){
//(n-m)!*C(n,m)
cout<<fac[n-m]*C(n,m)%mod<<"\n";
return;
}
//没有 0 或 1.
//怎么办?
//最后一步肯定是找
int mn=1ll<<60;
for(int i=1;i<=m;i++)mn=min(mn,a[i]);
//0~mn-1 得是在一起的.
//0~2.
//n-m-(mn-1)+1.
int v=fac[mn]*fac[n-m-(mn-1)]%mod;
v*=C(n-m-mn+2+m-1,m);
v%=mod;
cout<<v<<"\n";
}
signed main(){
fac[0]=1;
for(int i=1;i<=1000004;i++)fac[i]=fac[i-1]*i%mod;
ifac[1000004]=qkp(fac[1000004],mod-2);
for(int i=1000003;i>=0;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
int t=read();
while(t--)solve();
return 0;
}
//look at my code
//my code is amazing
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 15ms
memory: 16788kb
input:
100 4 4 3 0 1 2 3 1 0 5 2 1 3 5 3 1 4 2 5 3 0 4 2 3 1 0 5 1 3 3 3 1 2 0 3 1 0 4 3 0 2 3 4 2 0 2 5 1 ...
output:
1 6 60 20 20 6 36 1 6 4 12 36 1 20 24 4 4 12 1 1 12 24 4 1 3 60 20 18 8 1 2 2 1 120 1 36 20 12 5 60 ...
result:
wrong answer 7th lines differ - expected: '60', found: '36'
Test #2:
score: 0
Wrong Answer
time: 491ms
memory: 16788kb
input:
1000000 420929 1 239064 93187 1 85123 171379 1 110159 658643 1 0 303046 1 95912 800861 1 781035 9893...
output:
797817753 129838209 419745334 191686493 756093849 274621073 690958767 468869936 13727963 261935512 9...
result:
wrong answer 1st lines differ - expected: '598226497', found: '797817753'
Test #3:
score: 20
Accepted
time: 115ms
memory: 19316kb
input:
38765 832568 1 0 992725 6 548209 466528 628957 748938 0 578853 943934 15 863133 363066 513728 634152...
output:
485766967 626192578 109003053 452562070 536252017 398732909 215760199 971680463 57876225 982883068 7...
result:
ok 38765 lines
Test #4:
score: 20
Accepted
time: 61ms
memory: 19272kb
input:
38573 988634 10 800634 876452 811249 495916 842656 695203 0 914758 757887 237251 948749 6 282623 267...
output:
184333188 275156102 888302414 617843139 541399598 910523975 537526380 145847577 319719384 409299415 ...
result:
ok 38573 lines
Test #5:
score: 0
Wrong Answer
time: 82ms
memory: 18956kb
input:
38561 996249 6 150367 424546 851150 536915 420708 392670 956743 7 858128 296060 304111 814957 936254...
output:
73456740 468681063 172582040 822630413 735415939 823368682 209914325 370642897 303209059 460370732 6...
result:
wrong answer 1st lines differ - expected: '204801326', found: '73456740'