UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213031#3823. 艾特扣德drdilyor40557ms19316kbC++111.3kb2024-11-03 12:50:232024-11-03 13:02:31

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.
	//
	int v=fac[mn];
	v*=C(n-mn+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: 13ms
memory: 16784kb

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
18
1
6
4
12
18
1
20
24
4
4
12
1
1
12
24
4
1
3
60
20
18
8
1
2
2
1
120
1
18
20
12
5
60
...

result:

wrong answer 7th lines differ - expected: '60', found: '18'

Test #2:

score: 0
Wrong Answer
time: 301ms
memory: 16788kb

input:

1000000
420929 1
239064
93187 1
85123
171379 1
110159
658643 1
0
303046 1
95912
800861 1
781035
9893...

output:

858051628
176608687
338880936
191686493
410127684
34348972
15356292
897926996
9801724
903432433
1896...

result:

wrong answer 1st lines differ - expected: '598226497', found: '858051628'

Test #3:

score: 20
Accepted
time: 93ms
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: 76ms
memory: 19268kb

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: 74ms
memory: 18952kb

input:

38561
996249 6
150367 424546 851150 536915 420708 392670
956743 7
858128 296060 304111 814957 936254...

output:

774023176
367506897
866209256
55275576
206543667
7216993
792414453
793492016
12742652
915057973
1014...

result:

wrong answer 1st lines differ - expected: '204801326', found: '774023176'