QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#397109#7989. 三染色PertaAC ✓231ms13236kbC++145.0kb2024-04-23 16:43:232024-04-23 16:43:25

Judging History

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

  • [2024-04-23 16:43:25]
  • 评测
  • 测评结果:AC
  • 用时:231ms
  • 内存:13236kb
  • [2024-04-23 16:43:23]
  • 提交

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;
}

详细

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'