QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#292931 | #7989. 三染色 | vme50 | AC ✓ | 473ms | 331140kb | C++17 | 2.3kb | 2023-12-28 17:04:09 | 2023-12-28 17:04:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=55,M=5,C=505,MOD=998244353;
int n,m,S,pw[M],w[C],a[N][M];struct Node {int x,y;}ans,dp[N][M][N][M+1][C];
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
void W(int &x,ll y) {x=(x+y)%MOD;}
void W(Node &x,Node y,int w) {W(x.x,y.x);W(x.y,y.y);W(x.y,1ll*y.x*w);}
int f(int x,int y,int stt,int w)
{
if(y<m-2) {int t=w-stt/pw[y]%3+1;return stt+t*(pw[y]-(x?pw[m-2]:0));}
if(y==m-2) return stt%pw[m-2]+(w+1)*pw[m-2];return stt/3+(stt%3-w+1)*pw[m-2];
}
int main()
{
scanf("%d %d",&m,&n);pw[0]=1;for(int i=1;i<m;++i) pw[i]=pw[i-1]*3;
for(int i=0;i<m;++i) for(int j=0;j<n;++j) scanf("%d",&a[j][i]);
for(int i=0;i<pw[m-1];++i) for(int j=0;j<m-1;++j) w[i]+=(i/pw[j]%3)-1;
S=pw[m-2]*2;for(int i=0;i<m-2;++i) S+=pw[i];
for(int d=0;d<3;++d)
{
for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(a[i][j]<3) a[i][j]=(a[i][j]-d+3)%3;
for(int i=0;i<n;++i) for(int j=0;j<m;++j) for(int k=0;k<n+m;++k) for(int l=0;l<=m;++l)
for(int x=0;x<pw[m-2]*(j<m-1?5:3);++x) dp[i][j][k][l][x]=(Node) {0,0};
for(int k=0;k<n+m;++k) dp[0][0][k][m][S]=(Node) {1,0};
for(int i=0,t;i<n;++i) for(int j=0;j<m;++j)
{
for(int k=0;k<n+m;++k) if(a[i][j]<3 && k%3!=a[i][j]) for(int l=0;l<=m;++l)
for(int x=0;x<pw[m-2]*(j<m-1?5:3);++x) dp[i][j][k][l][x]=(Node) {0,0};
for(int l=j+1;l<m;++l) if(j<l) for(int x=0;x<pw[m-2]*(j<m-1?5:3);++x)
W(dp[i][j][0][j][x],dp[i][j][0][l][x],j-l+MOD),dp[i][j][0][l][x]=(Node) {0,0};
for(int x=0;x<pw[m-2]*(j<m-1?5:3);++x)
W(dp[i][j][0][j][x],dp[i][j][0][m][x],i+j),dp[i][j][0][m][x]=(Node) {0,0};
for(int k=0;k<n+m;++k) for(int l=0;l<=m;++l) if(j<m-1)
for(int x=0;x<pw[m-2]*5;++x)
{
t=x/pw[m-2]%5-2;
for(int y=max({t-1,-k,-1});y<=min({t+1,n+m-k-1,1});++y)
W(dp[i][j+1][k+y][l][f(i,j,x,y)],dp[i][j][k][l][x],0);
}
else for(int x=0;x<pw[m-1];++x)
{
t=k-w[x];
for(int y=max(-t,-1);y<=min(n+m-t-1,1);++y)
W(dp[i+1][0][t+y][l<m?max(l-1,0):m][f(i,j,x,y)],dp[i][j][k][l][x],0);
}
}for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(a[i][j]<3) a[i][j]=(a[i][j]+d)%3;
for(int k=0;k<n+m;++k) for(int l=0;l<m;++l) for(int x=0;x<pw[m-1];++x)
W(ans,dp[n-1][m-1][k][l][x],0);
}printf("%d %d\n",ans.x,ans.y);return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10120kb
input:
2 2 1 0 3 2
output:
1 2
result:
ok single line: '1 2'
Test #2:
score: 0
Accepted
time: 9ms
memory: 36692kb
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: 473ms
memory: 330516kb
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: 456ms
memory: 331140kb
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: 448ms
memory: 330680kb
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: 449ms
memory: 331040kb
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: 446ms
memory: 330684kb
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: 453ms
memory: 330684kb
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: 459ms
memory: 330692kb
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: 451ms
memory: 330448kb
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: 453ms
memory: 330456kb
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: 448ms
memory: 330556kb
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: 444ms
memory: 330716kb
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: 445ms
memory: 330716kb
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: 7ms
memory: 230084kb
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: 446ms
memory: 330584kb
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: 449ms
memory: 330592kb
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: 438ms
memory: 330624kb
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: 438ms
memory: 330404kb
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: 448ms
memory: 330828kb
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: 5ms
memory: 28916kb
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: 143ms
memory: 186952kb
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'