QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#397260#7989. 三染色yyyyxhAC ✓137ms6924kbC++143.4kb2024-04-23 20:51:042024-04-23 20:51:04

Judging History

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

  • [2024-04-23 20:51:04]
  • 评测
  • 测评结果:AC
  • 用时:137ms
  • 内存:6924kb
  • [2024-04-23 20:51:04]
  • 提交

answer

#include <cstdio>
using namespace std;
const int N=63,M=6,S=2187,P=998244353;
typedef long long ll;
const int D[3][3]={{0,1,-1},{-1,0,1},{1,-1,0}};
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=x*10+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
int n,m,nm,all,_all;
int pw[M+1];
int a[S][M];
int f[S][M+1];
int w[S][M+1];
bool ava[S][M+1][3];
int dp[S],_dp[S];
int g[S][N+M][M],_g[S][N+M][M];
int h[S][N+M],_h[S][N+M];
inline void inc(int &x,int v){(x+=v)>=P&&(x-=P);}
inline bool check(int a,int b,int c,int d){return D[a][b]+D[b][c]+D[c][d]+D[d][a]==0;}
void dfs(int x,int cur){
	if(x==m){
		++dp[cur];
		int mn=0,pos=0;
		for(int i=1;i<m;++i)
			if(mn>f[cur][i]) mn=f[cur][i],pos=i;
		if(pos) ++g[cur][-mn][pos];
		for(int i=-mn+1;i<nm;++i) ++h[cur][i];
		return;
	}
	for(int c=0;c<3;++c){
		if(a[0][x]!=3&&a[0][x]!=c) continue;
		dfs(x+1,cur+pw[x]*c);
	}
}
int main(){
	m=read();n=read();nm=n+m;
	for(int j=0;j<m;++j)
		for(int i=0;i<n;++i) a[i][j]=read();
	pw[0]=1;
	for(int i=1;i<=m;++i) pw[i]=pw[i-1]*3;
	_all=pw[m];all=_all*3;
	for(int s=0;s<all;++s){
		for(int i=0,tmp=s;i<=m;++i) w[s][i]=tmp%3,tmp/=3;
		for(int i=1;i<=m;++i) f[s][i]=f[s][i-1]+D[w[s][i-1]][w[s][i]];
		for(int i=1;i<m;++i)
			for(int c=0;c<3;++c) ava[s][i][c]=check(w[s][i-1],w[s][i],w[s][i+1],c);
	}
	dfs(0,0);
	for(int x=1;x<n;++x){
		for(int s=0;s<_all;++s){
			_dp[s]=dp[s],dp[s]=0;
			for(int t=0;t<nm;++t){
				_h[s][t]=h[s][t],h[s][t]=0;
				for(int p=0;p<m;++p) _g[s][t][p]=g[s][t][p],g[s][t][p]=0;
			}
		}
		for(int c=0;c<3;++c){
			if(a[x][0]!=3&&a[x][0]!=c) continue;
			for(int s=0;s<_all;++s){
				int _s=3*s+c;
				inc(dp[_s],_dp[s]);
				for(int t=0;t<nm;++t){
					int _t=t+D[s%3][c];
					if(_t<0) continue;
					if(!_t){
						inc(g[_s][0][0],(ll)_h[s][t]*x%P);
						for(int p=1;p<m;++p) inc(g[_s][0][0],(ll)_g[s][t][p]*x%P);
						inc(g[_s][0][0],_g[s][t][0]);
						continue;
					}
					inc(h[_s][_t],_h[s][t]);
					inc(g[_s][_t][0],_g[s][t][0]);
					inc(g[_s][_t][0],(ll)_g[s][t][1]*x%P);
					for(int p=2;p<m;++p) inc(g[_s][_t][p-1],_g[s][t][p]);
				}
			}
		}
		for(int i=1;i<m;++i){
			for(int s=0;s<all;++s){
				_dp[s]=dp[s],dp[s]=0;
				for(int t=0;t<nm;++t){
					_h[s][t]=h[s][t],h[s][t]=0;
					for(int p=0;p<m;++p) _g[s][t][p]=g[s][t][p],g[s][t][p]=0;
				}
			}
			for(int c=0;c<3;++c){
				if(a[x][i]!=3&&a[x][i]!=c) continue;
				for(int s=0;s<all;++s)
					if(ava[s][i][c]){
						int _s=s+(c-w[s][i])*pw[i];
						inc(dp[_s],_dp[s]);
						for(int t=0;t<nm;++t){
							int cf=t+f[_s][i];
							if(cf<0) continue;
							if(!cf){
								inc(g[_s][t][i],_h[s][t]);
								for(int p=i;p<m;++p) inc(g[_s][t][i],_g[s][t][p]);
								for(int p=0;p<i;++p) inc(g[_s][t][p],_g[s][t][p]);
								continue;
							}
							inc(h[_s][t],_h[s][t]);
							for(int p=0;p<m;++p) inc(g[_s][t][p],_g[s][t][p]);
						}
					}
			}
		}
		for(int s=_all;s<all;++s){
			int _s=s;
			while(_s>=_all) _s-=_all;
			inc(dp[_s],dp[s]),dp[s]=0;
			for(int t=0;t<nm;++t){
				inc(h[_s][t],h[s][t]),h[s][t]=0;
				for(int p=0;p<m;++p)
					inc(g[_s][t][p],g[s][t][p]),g[s][t][p]=0;
			}
		}
	}
	int res=0,ans=0;
	for(int i=0;i<_all;++i){
		inc(res,dp[i]);
		for(int t=0;t<nm;++t){
			inc(ans,g[i][t][0]);
			for(int p=1;p<m;++p) inc(ans,(ll)g[i][t][p]*(p+n-1)%P);
		}
	}
	printf("%d %d\n",res,ans);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

input:

2 2
1 0
3 2

output:

1 2

result:

ok single line: '1 2'

Test #2:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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'