QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#397109 | #7989. 三染色 | Perta | AC ✓ | 231ms | 13236kb | C++14 | 5.0kb | 2024-04-23 16:43:23 | 2024-04-23 16:43:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=7,M=65,K=750,mod=998244353;
int n,m,ans,pw[M],a[N][M];
int c[4],f[N][K],g[N][K][N+M][N];
inline void upd(int &x,int y) {x+=y;x=(x>=mod)?x-mod:x;}
int solve1()
{
for(int i=0;i<pw[n];i++)
{
bool flag=1;
for(int j=0;j<n;j++)
if(a[j][0]!=3&&i/pw[j]%3!=a[j][0]) {flag=0;break;}
if(!flag) continue;
for(int j=0;j<3;j++)
if(a[0][1]==3||a[0][1]==j) f[0][i*3+j]=1;
}
for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
for(int k=0;k<pw[n+1];k++) f[j][k]=0;
for(int k=0;k<pw[n+1];k++)
for(int p=0;p<3;p++)
{
if(a[j][i]!=3&&a[j][i]!=p) continue;
c[0]=k/pw[j-1]%3;
c[1]=k/pw[j]%3;
c[2]=k/pw[j+1]%3;
c[3]=p;
int ck=0;
for(int h=0;h<4;h++) ck+=(c[h]==c[(h+1)%4]);
if(ck!=1)
upd(f[j][(k/pw[j+1]*3+p)*pw[j]+k%pw[j]],f[j-1][k]);
}
}
if(i==m-1) break;
for(int j=0;j<pw[n+1];j++) f[0][j]=0;
for(int j=0;j<pw[n+1];j++)
for(int k=0;k<3;k++)
if(a[0][i+1]==3||a[0][i+1]==k) upd(f[0][j%pw[n]*3+k],f[n-1][j]);
}
ans=0;
for(int i=0;i<pw[n+1];i++) upd(ans,f[n-1][i]);
return ans;
}
int solve2()
{
ans=0;
for(int j=0;j<pw[n];j++)
{
bool flag=1;
for(int k=0;k<n;k++)
if(a[k][0]!=3&&j/pw[k]%3!=a[k][0]) {flag=0;break;}
if(!flag) continue;
int S=0,Mn=0,loc=0;
for(int k=1;k<n;k++)
{
for(int p=-1;p<2;p++)
if((j/pw[k-1]+p+3)%3==j/pw[k]%3) S+=p;
if(S<Mn) Mn=S,loc=k;
}
for(int k=0;k<3;k++)
if(a[0][1]==3||a[0][1]==k)
{
int ck=0;
for(int p=-1;p<2;p++)
if((j%3+p+3)%3==k) ck=p;
for(int p=-Mn;p<n+m-1;p++)
if(p+ck>=0&&p+ck<n+m-1)
{
if(p==-Mn)
if(loc) upd(g[0][j*3+k][p+ck][(p+ck)?loc-1:0],1);
else upd(g[0][j*3+k][p+ck][n],0);
else upd(g[0][j*3+k][p+ck][(p+ck)?n+1:0],1);
}
}
}
for(int j=1;j<m;j++)
{
for(int k=1;k<n;k++)
{
for(int p=0;p<pw[n+1];p++)
for(int h=0;h<n+m-1;h++)
for(int x=0;x<n+2;x++) g[k][p][h][x]=0;
for(int p=0;p<pw[n+1];p++)
for(int h=0;h<3;h++)
{
if(a[k][j]!=3&&a[k][j]!=h) continue;
c[0]=p/pw[k-1]%3;
c[1]=p/pw[k]%3;
c[2]=p/pw[k+1]%3;
c[3]=h;
int ck=0;
for(int x=0;x<4;x++) ck+=(c[x]==c[(x+1)%4]);
if(ck==1) continue;
for(int x=-1;x<2;x++)
if((c[0]+x+3)%3==h) ck=x;
for(int th=0;th<n+m-1;th++)
if(th+ck>=0&&th+ck<n+m-1)
for(int x=0;x<n+2;x++)
upd(g[k][(p/pw[k+1]*3+h)*pw[k]+p%pw[k]][th+ck][(th+ck)?x:x==n?n:min(x,k)],g[k-1][p][th][x]);
}
}
if(j==m-1) break;
for(int k=0;k<pw[n+1];k++)
for(int p=0;p<n+m-1;p++)
for(int h=0;h<n+2;h++) g[0][k][p][h]=0;
for(int k=0;k<pw[n+1];k++)
for(int p=0;p<3;p++)
if(a[0][j+1]==3||a[0][j+1]==p)
{
int S=0,ck=0;
for(int h=n-1;h;h--)
{
for(int x=-1;x<2;x++)
if((k/pw[h]+x+3)%3==k/pw[h-1]%3) ck=x;
S+=ck;
}
for(int h=-1;h<2;h++)
if((k%3+h+3)%3==p) ck=h;
for(int h=0;h<n+m-1;h++)
if(S+h+ck>=0&&S+h+ck<n+m-1)
{
upd(g[0][k%pw[n]*3+p][S+h+ck][n],1ll*j*g[n-1][k][h][0]%mod);
for(int x=1;x<n+2;x++)
upd(g[0][k%pw[n]*3+p][S+h+ck][(S+h+ck)?x-(x<n):x==n?x:0],g[n-1][k][h][x]);
}
}
}
for(int j=0;j<pw[n+1];j++)
for(int k=0;k<n+m-1;k++)
{
upd(ans,g[n-1][j][k][n]);
for(int p=0;p<n;p++)
upd(ans,1ll*(m-1+p)*g[n-1][j][k][p]%mod);
}
return ans;
}
int main()
{
pw[0]=1;
for(int i=1;i<=10;i++) pw[i]=3*pw[i-1];
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++) scanf("%d",a[i]+j);
printf("%d %d\n",solve1(),solve2());
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3988kb
input:
2 2 1 0 3 2
output:
1 2
result:
ok single line: '1 2'
Test #2:
score: 0
Accepted
time: 3ms
memory: 13236kb
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: 207ms
memory: 12376kb
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: 231ms
memory: 11836kb
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: 224ms
memory: 13036kb
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: 196ms
memory: 11636kb
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: 204ms
memory: 12716kb
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: 182ms
memory: 12816kb
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: 213ms
memory: 11600kb
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: 205ms
memory: 12312kb
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: 168ms
memory: 12412kb
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: 201ms
memory: 11316kb
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: 174ms
memory: 12240kb
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: 177ms
memory: 13036kb
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: 3ms
memory: 4036kb
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: 216ms
memory: 11904kb
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: 225ms
memory: 12972kb
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: 215ms
memory: 11852kb
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: 224ms
memory: 12544kb
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: 225ms
memory: 13208kb
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: 6ms
memory: 13204kb
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: 79ms
memory: 12604kb
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'