QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#377281#7989. 三染色C1942huangjiaxuAC ✓116ms25232kbC++142.3kb2024-04-05 11:15:052024-04-05 11:15:06

Judging History

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

  • [2024-04-05 11:15:06]
  • 评测
  • 测评结果:AC
  • 用时:116ms
  • 内存:25232kb
  • [2024-04-05 11:15:05]
  • 提交

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]],M;
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);
	M=pw[n];
	for(int i=0;i<n;++i)for(int j=1;j<=m;++j)scanf("%d",&a[i][j]);
	for(int S=0;S<M;++S)for(int i=0;i<n;++i)st[S][i]=S/pw[i]%3;
	for(int S=0;S<M;++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<M;++S)chk[i][S]=checkS(i,S);
	for(int S=0;S<M;++S)for(int T=0;T<M;++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<M;++S)if(chk[m][S])g[m][S][0]=1;
	for(int i=m;i>1;--i)for(int S=0;S<M;++S)if(chk[i][S])
		for(int j=0;j+i<n+m;++j)if(g[i][S][j])
			for(int T=0;T<M;++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<M;++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<M;++S)if(chk[1][S])f[1][S][0][pmx[S]]=1;
	for(int i=1;i<m;++i)for(int S=0;S<M;++S)if(chk[i][S]){
		vector<int>tmp;
		for(int T=0;T<M;++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]%P;
			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<M;++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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
1 0
3 2

output:

1 2

result:

ok single line: '1 2'

Test #2:

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

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: 0
Accepted
time: 26ms
memory: 18920kb

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:

988900801 3995091

result:

ok single line: '988900801 3995091'

Test #4:

score: 0
Accepted
time: 115ms
memory: 25184kb

input:

5 50
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...

output:

442413777 294837747

result:

ok single line: '442413777 294837747'

Test #5:

score: 0
Accepted
time: 77ms
memory: 25232kb

input:

5 50
3 3 3 3 3 3 3 1 3 3 3 3 3 3 3 3 3 3 3 2 3 3 3 1 3 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 1 3 3
3 3 3 3 3 3 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 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 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 3 3 3 3...

output:

225441044 884828241

result:

ok single line: '225441044 884828241'

Test #6:

score: 0
Accepted
time: 28ms
memory: 18060kb

input:

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

output:

864217599 942336468

result:

ok single line: '864217599 942336468'

Test #7:

score: 0
Accepted
time: 33ms
memory: 19048kb

input:

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

output:

436364669 329259414

result:

ok single line: '436364669 329259414'

Test #8:

score: 0
Accepted
time: 0ms
memory: 15344kb

input:

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

output:

0 0

result:

ok single line: '0 0'

Test #9:

score: 0
Accepted
time: 69ms
memory: 22744kb

input:

5 50
3 3 3 3 3 3 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 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3
3 3 3 3 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 3 3 3 3 3 3 3 3 3 3 1 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 1 3 3 3 3 3 3 3 3 3 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 3...

output:

810142538 871482893

result:

ok single line: '810142538 871482893'

Test #10:

score: 0
Accepted
time: 34ms
memory: 19356kb

input:

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

output:

751568411 253164328

result:

ok single line: '751568411 253164328'

Test #11:

score: 0
Accepted
time: 7ms
memory: 13720kb

input:

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

output:

0 0

result:

ok single line: '0 0'

Test #12:

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

input:

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

output:

0 0

result:

ok single line: '0 0'

Test #13:

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

input:

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

output:

200661729 258704668

result:

ok single line: '200661729 258704668'

Test #14:

score: 0
Accepted
time: 0ms
memory: 15428kb

input:

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

output:

0 0

result:

ok single line: '0 0'

Test #15:

score: 0
Accepted
time: 2ms
memory: 6916kb

input:

2 50
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

output:

780628942 499420229

result:

ok single line: '780628942 499420229'

Test #16:

score: 0
Accepted
time: 67ms
memory: 23756kb

input:

5 50
3 0 3 3 3 3 3 3 3 3 3 3 3 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 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 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 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 3 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...

output:

798118080 776193618

result:

ok single line: '798118080 776193618'

Test #17:

score: 0
Accepted
time: 101ms
memory: 23908kb

input:

5 50
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 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 3 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 3 3 3 3 3...

output:

622800277 243172909

result:

ok single line: '622800277 243172909'

Test #18:

score: 0
Accepted
time: 74ms
memory: 24404kb

input:

5 50
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 3 3 3 2 3 3 2 3 3 3 3 3 1 3 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 3 3 3 3 3 3 3 3 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 3 2 2 3 3 3 3 3 3 3 3 3 3 3 3 0 3 3 2 3 3 3 3 3 3 3...

output:

480284116 641719784

result:

ok single line: '480284116 641719784'

Test #19:

score: 0
Accepted
time: 106ms
memory: 24932kb

input:

5 50
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...

output:

442413777 294837747

result:

ok single line: '442413777 294837747'

Test #20:

score: 0
Accepted
time: 116ms
memory: 24932kb

input:

5 50
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...

output:

442413777 294837747

result:

ok single line: '442413777 294837747'

Test #21:

score: 0
Accepted
time: 3ms
memory: 6316kb

input:

5 4
3 3 3 3
3 3 3 3
3 3 3 3
3 3 3 3
3 3 3 3

output:

62340543 139608630

result:

ok single line: '62340543 139608630'

Test #22:

score: 0
Accepted
time: 39ms
memory: 17312kb

input:

5 28
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

output:

585830006 459695279

result:

ok single line: '585830006 459695279'