QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#746472#9611. 木桶效应ANIG8 21ms3680kbC++141014b2024-11-14 14:45:582024-11-14 14:45:59

Judging History

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

  • [2024-11-14 14:45:59]
  • 评测
  • 测评结果:8
  • 用时:21ms
  • 内存:3680kb
  • [2024-11-14 14:45:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=55,M=1e5+5,mods=998244353;
int pows(int a,int b){
	if(b==0)return 1;
	int res=pows(a,b>>1);
	res=res*res%mods;
	if(b&1)res=res*a%mods;
	return res;
}
int n,m,qs,f[N][N],jc[M],ny[M];
int C(int a,int b){
	if(a<0||b<0||a<b)return 0;
	return jc[a]*ny[b]%mods*ny[a-b]%mods;
}
signed main(){
	cin>>n>>m>>qs;
	jc[0]=ny[0]=1;
	for(int i=1;i<=n*m;i++)jc[i]=jc[i-1]*i%mods,ny[i]=pows(jc[i],mods-2);
	f[0][n]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=n;j++){
			for(int k=0;k<=j;k++){
				for(int l=0;l<=m;l++){
					int ans=0;
					for(int r=0;r<=k;r++){
						int tmp=pows(k-r,m-l)*C(k,r)%mods;
						if(r&1)ans-=tmp;
						else ans+=tmp;
					}
					ans%=mods;
					f[i+1][j-k]+=f[i][j]*C(m,l)%mods*pows(n-j-i,l)%mods*ans%mods*pows(i+1,k)%mods*C(j,k)%mods;
				}
			}
		}
		for(int j=0;j<=n;j++){
			f[i+1][j]%=mods;
	//		cout<<i+1<<" "<<j<<" "<<f[i+1][j]<<endl;
		}
	}
	cout<<(f[n][0]+mods)%mods;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 4
Accepted
time: 0ms
memory: 3556kb

input:

5 3 0

output:

21412920

result:

ok single line: '21412920'

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 3596kb

input:

5 3 2
3 4 4
2 5 3

output:

21412920

result:

wrong answer 1st lines differ - expected: '847674', found: '21412920'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 8
Accepted

Test #7:

score: 8
Accepted
time: 10ms
memory: 3680kb

input:

50 1 0

output:

263941435

result:

ok single line: '263941435'

Test #8:

score: 8
Accepted
time: 12ms
memory: 3612kb

input:

43 2 0

output:

136378346

result:

ok single line: '136378346'

Test #9:

score: 8
Accepted
time: 21ms
memory: 3572kb

input:

50 2 0

output:

489087596

result:

ok single line: '489087596'

Subtask #4:

score: 0
Runtime Error

Dependency #3:

100%
Accepted

Test #10:

score: 0
Runtime Error

input:

50 292247015 0

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%

Subtask #8:

score: 0
Skipped

Dependency #7:

0%

Subtask #9:

score: 0
Skipped

Dependency #8:

0%