QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#751276#9611. 木桶效应ANIG48 2950ms26696kbC++142.5kb2024-11-15 17:51:252024-11-15 17:51:26

Judging History

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

  • [2024-11-15 17:51:26]
  • 评测
  • 测评结果:48
  • 用时:2950ms
  • 内存:26696kb
  • [2024-11-15 17:51:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=55,M=(1<<10)+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;
}
struct node{
	int x,y,w;
}g[N];
int n,m,qs,sz,f[N][N][M],cnt[M],jc[M],ny[M],bh[N],idx;
vector<int>zj[M],dy[N];
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(){
	vector<int>jl;
	auto fd=[&](int x){
		return lower_bound(jl.begin(),jl.end(),x)-jl.begin();
	};
	cin>>n>>m>>qs;
	for(int i=1;i<=qs;i++){
		cin>>g[i].x>>g[i].y>>g[i].w;
		if(!bh[g[i].y])bh[g[i].y]=++idx;
		jl.push_back(g[i].x);
	}
	for(int i=0;i<(1<<idx);i++){
		for(int j=i;j;j=j-1&i)zj[i].push_back(j);
		zj[i].push_back(0);
		cnt[i]=__builtin_popcount(i);
	}
	sort(jl.begin(),jl.end());
	jl.resize(unique(jl.begin(),jl.end())-jl.begin());
	for(int i=1;i<=qs;i++)dy[fd(g[i].x)].push_back(i);
	sz=jl.size();
	jc[0]=ny[0]=1;
	for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i%mods,ny[i]=pows(jc[i],mods-2);
	f[0][n-idx][(1<<idx)-1]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=n-idx;j++){
			for(int k=0;k<(1<<idx);k++){
			    for(int l=0;l<=j;l++){
			    	for(auto t:zj[k]){
			    		int ans=0;
			    		for(int r=0;r<=l;r++){
			    			int sm=0;
			    			for(auto s:zj[t]){
			    				int tmp=pows(n-i-(j-l)-r-(cnt[k]-cnt[t])-cnt[s],m-sz);
			    				for(int u=0;u<sz;u++){
			    					int sm=n-i-(j-l)-r-(cnt[k]-cnt[t])-cnt[s],op=0;
			    					for(auto d:dy[u]){
			    						if((s>>bh[g[d].y]-1&1^1)&&((k^t)>>bh[g[d].y]-1&1^1)&&g[d].w>i+1)sm--;
			    						if(g[d].w==i+1)op=bh[g[d].y];
			    					}
			    					if(op){
			    						if((k^t)>>op-1&1)sm=0;
			    						else if(s>>op-1&1)sm=0;
			    						else sm=1;
			    					}
			    			//		cout<<i<<" "<<j<<" "<<k<<" "<<l<<" "<<t<<" "<<s<<" "<<tmp<<" "<<u<<" "<<sm<<" "<<op<<endl;
			    					tmp=tmp*sm%mods;
			    				}
			    			//	cout<<i<<" "<<j<<" "<<k<<" "<<l<<" "<<t<<" "<<s<<" "<<tmp<<endl;
			    				if(cnt[s]&1)sm-=tmp;
			    				else sm+=tmp;
			    			}
			    			sm%=mods;
			    			if(r&1)ans-=sm*C(l,r)%mods;
			    			else ans+=sm*C(l,r)%mods;
			    		}
						ans%=mods;
			    		f[i+1][j-l][k^t]+=f[i][j][k]*ans%mods*pows(i+1,l+cnt[t])%mods*C(j,l)%mods;
			    	}
			    }
			}
		}
		for(int j=0;j<=n-idx;j++){
			for(int k=0;k<(1<<idx);k++){
				f[i+1][j][k]%=mods;
			//	cout<<i+1<<" "<<j<<" "<<k<<" "<<f[i+1][j][k]<<endl;
			}
		}
	}
	cout<<(f[n][0][0]+mods)%mods;
}

详细

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 1ms
memory: 5700kb

input:

5 3 0

output:

21412920

result:

ok single line: '21412920'

Test #2:

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

input:

5 3 2
3 4 4
2 5 3

output:

847674

result:

ok single line: '847674'

Test #3:

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

input:

5 3 3
3 5 5
1 2 5
2 5 3

output:

168780

result:

ok single line: '168780'

Subtask #2:

score: 8
Accepted

Dependency #1:

100%
Accepted

Test #4:

score: 8
Accepted
time: 1ms
memory: 5788kb

input:

7 3 0

output:

160221085

result:

ok single line: '160221085'

Test #5:

score: 8
Accepted
time: 1ms
memory: 5732kb

input:

7 3 2
1 1 5
1 6 2

output:

598007855

result:

ok single line: '598007855'

Test #6:

score: 8
Accepted
time: 1ms
memory: 7684kb

input:

7 3 3
1 1 5
2 6 3
2 1 7

output:

950880222

result:

ok single line: '950880222'

Subtask #3:

score: 8
Accepted

Test #7:

score: 8
Accepted
time: 8ms
memory: 26696kb

input:

50 1 0

output:

263941435

result:

ok single line: '263941435'

Test #8:

score: 8
Accepted
time: 8ms
memory: 22308kb

input:

43 2 0

output:

136378346

result:

ok single line: '136378346'

Test #9:

score: 8
Accepted
time: 13ms
memory: 26192kb

input:

50 2 0

output:

489087596

result:

ok single line: '489087596'

Subtask #4:

score: 12
Accepted

Dependency #3:

100%
Accepted

Test #10:

score: 12
Accepted
time: 190ms
memory: 25056kb

input:

50 292247015 0

output:

226872193

result:

ok single line: '226872193'

Test #11:

score: 12
Accepted
time: 159ms
memory: 26100kb

input:

50 873009728 0

output:

63648791

result:

ok single line: '63648791'

Subtask #5:

score: 16
Accepted

Dependency #2:

100%
Accepted

Dependency #4:

100%
Accepted

Test #12:

score: 16
Accepted
time: 2950ms
memory: 13872kb

input:

20 728836785 5
248289571 15 16
439110385 8 15
339467267 12 7
585491339 7 9
605518440 4 1

output:

761275883

result:

ok single line: '761275883'

Test #13:

score: 16
Accepted
time: 2607ms
memory: 11912kb

input:

20 288197925 5
31379347 9 1
222153278 1 1
24531748 20 1
106427339 18 1
212338331 17 1

output:

877851586

result:

ok single line: '877851586'

Test #14:

score: 16
Accepted
time: 2940ms
memory: 14148kb

input:

20 880439688 5
563540321 17 20
395236367 3 20
300712779 6 20
121406689 18 20
25890496 9 20

output:

186649553

result:

ok single line: '186649553'

Test #15:

score: 16
Accepted
time: 266ms
memory: 12084kb

input:

20 311402369 5
311293636 14 13
306211116 19 19
36858994 5 11
36858994 19 10
306211116 14 18

output:

415461922

result:

ok single line: '415461922'

Test #16:

score: 16
Accepted
time: 783ms
memory: 13888kb

input:

20 98953332 5
1075868 12 5
31161114 8 12
46790018 9 10
39214697 15 7
46790018 8 8

output:

204149614

result:

ok single line: '204149614'

Subtask #6:

score: 0
Time Limit Exceeded

Dependency #5:

100%
Accepted

Test #17:

score: 0
Time Limit Exceeded

input:

50 915702052 5
541920465 39 16
833447607 49 14
326677362 14 34
412319566 10 36
206682128 46 28

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #6:

0%

Subtask #8:

score: 0
Skipped

Dependency #7:

0%

Subtask #9:

score: 0
Skipped

Dependency #8:

0%