QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#377275#7989. 三染色C1942huangjiaxuWA 23ms18880kbC++142.4kb2024-04-05 11:05:592024-04-05 11:06:00

Judging History

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

  • [2024-04-05 11:06:00]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:18880kb
  • [2024-04-05 11:05:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int P=998244353;
constexpr int pw[6]={1,3,9,27,81,243},w[3][3]={{0,-1,1},{1,0,-1},{-1,1,0}};
int n,m,a[5][55],st[pw[5]][5],ans1,ans2,mx[pw[5]],pmx[pw[5]],d[pw[5]][pw[5]];
bool chk[55][pw[5]],ok[pw[5]][pw[5]];
int f[55][pw[5]][61][6],g[55][pw[5]][61];
inline void Add(int &x,int y){
	if((x+=y)>=P)x-=P;
}
bool checkS(int x,int S){
	for(int i=0;i<n;++i)if(a[i][x]!=3&&st[S][i]!=a[i][x])return false;
	return true;
}
bool check(int S,int T){
	int x[4];
	for(int i=1;i<n;++i){
		x[0]=st[S][i-1],x[1]=st[S][i],x[2]=st[T][i],x[3]=st[T][i-1];
		for(int j=0;j<4;++j)
			if(x[j]==x[j+1&3]&&x[j]!=x[j+2&3]&&x[j]!=x[j+3&3]&&x[j+2&3]!=x[j+3&3])return false;
	}
	return true;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i)for(int j=1;j<=m;++j)scanf("%d",&a[i][j]);
	for(int S=0;S<pw[n];++S)for(int i=0;i<n;++i)st[S][i]=S/pw[i]%3;
	for(int S=0;S<pw[n];++S){
		mx[S]=pmx[S]=0;
		for(int i=1,v=0;i<n;++i){
			v+=w[st[S][i-1]][st[S][i]];
			if(v>mx[S])mx[S]=v,pmx[S]=i;
		}
	}
	for(int i=1;i<=m;++i)for(int S=0;S<pw[n];++S)chk[i][S]=checkS(i,S);
	for(int S=0;S<pw[n];++S)for(int T=0;T<pw[n];++T)ok[S][T]=check(S,T),d[S][T]=mx[S]-w[st[S][0]][st[T][0]]-mx[T];
	for(int S=0;S<pw[n];++S)if(chk[m][S])g[m][S][0]=1;
	for(int i=m;i>1;--i)for(int S=0;S<pw[n];++S)if(chk[i][S])
		for(int j=0;j+i<n+m;++j)if(g[i][S][j])
			for(int T=0;T<pw[n];++T)if(chk[i-1][T]&&ok[S][T]){
				Add(g[i-1][T][max(0,j+d[S][T])],g[i][S][j]);
			}
	for(int i=1;i<=m;++i)for(int S=0;S<pw[n];++S)
		for(int j=1;j+i<n+m;++j)Add(g[i][S][j],g[i][S][j-1]);
	for(int S=0;S<pw[n];++S)if(chk[1][S])f[1][S][0][pmx[S]]=1;
	for(int i=1;i<m;++i)for(int S=0;S<pw[n];++S)if(chk[i][S]){
		vector<int>tmp;
		for(int T=0;T<pw[n];++T)if(chk[i+1][T]&&ok[S][T])tmp.emplace_back(T);
		for(int j=0;j<i+n-1;++j){
			Add(f[i][S][j+1][n],f[i][S][j][0]);
			int w=1ll*f[i][S][j][0]*g[i][S][j];
			Add(ans1,w);
			Add(ans2,1ll*w*(i-1)%P);
			for(int k=1;k<=n;++k)if(f[i][S][j][k]){
				int t=k<n?k-1:n,v=f[i][S][j][k];
				for(auto T:tmp){
					int o=d[S][T]+j;
					if(o>0)Add(f[i+1][T][o][t],v);
					else if(!o)Add(f[i+1][T][o][min(t,pmx[T])],v);
					else Add(f[i+1][T][0][pmx[T]],v);
				}
			}
		}
	}
	for(int S=0;S<pw[n];++S)for(int j=0;j<m+n-1;++j)for(int k=0;k<n;++k){
		int v=f[m][S][j][k];
		Add(ans1,v);
		Add(ans2,1ll*v*(m-1+k)%P);
	}
	printf("%d %d\n",ans1,ans2);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5836kb

input:

2 2
1 0
3 2

output:

1 2

result:

ok single line: '1 2'

Test #2:

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

input:

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

output:

50830224 170059345

result:

ok single line: '50830224 170059345'

Test #3:

score: -100
Wrong Answer
time: 23ms
memory: 18880kb

input:

5 50
3 3 3 3 3 3 3 3 1 0 3 3 3 1 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 1 3 3 1 3 3 1 3 3 3 3 3 3 3 3 3 1 3 3 3 3 2 3 3 3 3 2 0 3 0 3 3 3 0 3 3 3 3 3 3 3 0 0 3 3 3 3
1 3 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 3 3 1 3 3 1 3 3 3 0 1 3 3 3 0 3 3 3 3 3 2 3 3 1 3 3 0 3 3 3...

output:

101778607 62263736

result:

wrong answer 1st lines differ - expected: '988900801 3995091', found: '101778607 62263736'