QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353022#7989. 三染色ucup-team1004WA 1ms3764kbC++143.0kb2024-03-13 19:49:362024-03-13 19:49:36

Judging History

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

  • [2024-03-13 19:49:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3764kb
  • [2024-03-13 19:49:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) (a).begin(),(a).end()
#ifdef DEBUG
template<class T>
ostream& operator << (ostream &out,vector<T> a){
	out<<'[';
	for(T x:a)out<<x<<',';
	return out<<']';
}
template<class T>
vector<T> ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
	cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
	cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
const int N=5,M=51,K=pow(3,N)+3,mod=998244353;
const int w[3][3]={{0,-1,1},{1,0,-1},{-1,1,0}};
int n,m,a[N][M];
int v[K][N],is[M][K],ok[K][K],mx[K],cur[K];
bool chk(int a,int b,int c,int d){
	return !((1<<a|1<<b|1<<c|1<<d)==7&&(a==b||b==c||c==d||d==a));
}
int f[M][K][M+N][N+1],g[M][K][M+N];
#define add(x,y) ((x)+=(y)>=mod&&((x)-=mod))
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=1;j<=m;j++)cin>>a[i][j];
	}
	int U=pow(3,n)-0.5;
	for(int S=0;S<=U;S++){
		for(int i=0,x=S;i<n;i++){
			v[S][i]=x%3,x/=3;
		}
	}
	for(int j=1;j<=m;j++){
		for(int S=0;S<=U;S++){
			is[j][S]=1;
			for(int i=0;i<n;i++){
				if(a[i][j]!=3&&a[i][j]!=v[S][i])is[j][S]=0;
			}
		}
	}
	for(int S=0;S<=U;S++){
		mx[S]=cur[S]=0;
		for(int i=1,x=0;i<n;i++){
			x+=w[v[S][i-1]][v[S][i]];
			if(x>mx[S])mx[S]=x,cur[S]=i;
		}
	}
	for(int S=0;S<=U;S++){
		for(int T=0;T<=U;T++){
			ok[S][T]=1;
			for(int i=0;i+1<n;i++){
				if(!chk(v[S][i],v[T][i],v[T][i+1],v[S][i+1]))ok[S][T]=0;
			}
		}
	}
	for(int S=0;S<=U;S++)if(is[m][S]){
		g[m][S][0]=1;
	}
	for(int i=m;i>1;i--){
		for(int S=0;S<=U;S++)if(is[i][S]){
			for(int p=0;p<m-i+n;p++){
				if(!g[i][S][p])continue;
				for(int T=0;T<=U;T++)if(is[i-1][T]&&ok[T][S]){
					int q=p+mx[S]-w[v[S][0]][v[T][0]]-mx[T];
					add(g[i-1][T][max(q,0)],g[i][S][p]);
				}	
			}
		}
	}
	for(int i=1;i<=m;i++){
		for(int S=0;S<=U;S++){
			for(int p=1;p<m-i+n;p++){
				add(g[i][S][p],g[i][S][p-1]);
			}
		}
	}
	for(int S=0;S<=U;S++)if(is[1][S]){
		f[1][S][0][cur[S]]=1;
	}
	int ans1=0,ans2=0;
	for(int i=1;i<m;i++){
		int lim=i-1+n;
		for(int S=0;S<=U;S++)if(is[i][S]){
			vector<int>pos;
			for(int T=0;T<=U;T++){
				if(is[i+1][T]&&ok[S][T])pos.push_back(T);
			}
			for(int p=0;p<lim;p++){
				add(f[i][S][p+1][n],f[i][S][p][0]);
				int cnt=1ll*f[i][S][p][0]*g[i][S][p]%mod;
				add(ans1,cnt);
				ans2=(ans2+1ll*cnt*(i-1))%mod;
				for(int d=1;d<=n;d++){
					if(!f[i][S][p][d])continue;
					int t=d<n?d-1:n;
					for(int T:pos){
						int q=p+mx[S]-w[v[S][0]][v[T][0]]-mx[T];
						if(q>0){
							add(f[i+1][T][q][t],f[i][S][p][d]);
						}else if(q==0){
							add(f[i+1][T][q][min(t,cur[T])],f[i][S][p][d]);
						}else{
							add(f[i+1][T][0][cur[T]],f[i][S][p][d]);
						}
					}
				}
			}
		}
	}
	for(int S=0;S<=U;S++){
		int lim=n+m-1;
		for(int p=0;p<lim;p++){
			for(int d=0;d<n;d++){
				add(ans1,f[m][S][p][d]);
				ans2=(ans2+1ll*(m-1+d)*f[m][S][p][d])%mod;
			}
		}
	}
	cout<<ans1<<' '<<ans2<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3764kb

input:

2 2
1 0
3 2

output:

0 0

result:

wrong answer 1st lines differ - expected: '1 2', found: '0 0'