QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#751294#9611. 木桶效应ANIG60 1272ms141424kbC++142.5kb2024-11-15 17:59:142024-11-15 17:59:18

Judging History

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

  • [2024-11-15 17:59:18]
  • 评测
  • 测评结果:60
  • 用时:1272ms
  • 内存:141424kb
  • [2024-11-15 17:59:14]
  • 提交

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],pw[N],cnt[M],jc[M],ny[M],bh[N],idx,dp[N][M][M];
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();
	for(int i=0;i<=n;i++)pw[i]=pows(i,m-sz);
	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;j++){
			for(int k=0;k<(1<<idx);k++){
				for(auto s:zj[k^(1<<idx)-1]){
    				int tmp=pw[j-cnt[k]-cnt[s]];
    				for(int u=0;u<sz;u++){
    					int sm=j-cnt[k]-cnt[s],op=0;
    					for(auto d:dy[u]){
    						if((s>>bh[g[d].y]-1&1^1)&&(k>>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>>op-1&1)sm=0;
    						else if(s>>op-1&1)sm=0;
    						else sm=1;
    					}
    					tmp=tmp*sm%mods;
    				}
    				dp[j][k][s]=tmp;
				}
			}
		}
		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&&n-i-(j-l)-r>=0;r++){
			    			int sm=0;
			    			for(auto s:zj[t]){
							    int tmp=dp[n-i-(j-l)-r][k^t][s];
							    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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4
Accepted

Test #1:

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

input:

5 3 0

output:

21412920

result:

ok single line: '21412920'

Test #2:

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

input:

5 3 2
3 4 4
2 5 3

output:

847674

result:

ok single line: '847674'

Test #3:

score: 4
Accepted
time: 2ms
memory: 15944kb

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: 0ms
memory: 22304kb

input:

7 3 0

output:

160221085

result:

ok single line: '160221085'

Test #5:

score: 8
Accepted
time: 2ms
memory: 20044kb

input:

7 3 2
1 1 5
1 6 2

output:

598007855

result:

ok single line: '598007855'

Test #6:

score: 8
Accepted
time: 0ms
memory: 20100kb

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

input:

50 1 0

output:

263941435

result:

ok single line: '263941435'

Test #8:

score: 8
Accepted
time: 4ms
memory: 110396kb

input:

43 2 0

output:

136378346

result:

ok single line: '136378346'

Test #9:

score: 8
Accepted
time: 7ms
memory: 129296kb

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: 3ms
memory: 128532kb

input:

50 292247015 0

output:

226872193

result:

ok single line: '226872193'

Test #11:

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

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: 26ms
memory: 61008kb

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: 33ms
memory: 59140kb

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: 33ms
memory: 59276kb

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: 6ms
memory: 52956kb

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: 17ms
memory: 53072kb

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: 12
Accepted

Dependency #5:

100%
Accepted

Test #17:

score: 12
Accepted
time: 1272ms
memory: 140940kb

input:

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

output:

783441394

result:

ok single line: '783441394'

Test #18:

score: 12
Accepted
time: 1269ms
memory: 141264kb

input:

50 47879239 5
30666754 20 1
23945845 17 1
27229141 25 1
40551703 9 1
15723198 18 1

output:

546399382

result:

ok single line: '546399382'

Test #19:

score: 12
Accepted
time: 1252ms
memory: 141424kb

input:

50 334191703 5
167838076 19 50
95127599 33 50
221030062 4 50
89223523 36 50
40736662 39 50

output:

242104112

result:

ok single line: '242104112'

Test #20:

score: 12
Accepted
time: 130ms
memory: 130564kb

input:

50 33538004 5
1341436 40 26
19132404 4 13
22271562 24 25
19132404 40 18
19132404 24 38

output:

509216038

result:

ok single line: '509216038'

Test #21:

score: 12
Accepted
time: 408ms
memory: 135352kb

input:

50 453197583 5
304895210 17 41
450727109 33 20
129855576 4 24
214262208 12 46
214262208 4 27

output:

929330226

result:

ok single line: '929330226'

Subtask #7:

score: 0
Time Limit Exceeded

Dependency #6:

100%
Accepted

Test #22:

score: 0
Time Limit Exceeded

input:

50 733592974 7
204969642 20 32
532101473 38 22
428067108 29 19
699479674 23 35
403248947 11 33
523610998 39 50
207894041 37 47

output:


result:


Subtask #8:

score: 0
Skipped

Dependency #7:

0%

Subtask #9:

score: 0
Skipped

Dependency #8:

0%