QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#377275 | #7989. 三染色 | C1942huangjiaxu | WA | 23ms | 18880kb | C++14 | 2.4kb | 2024-04-05 11:05:59 | 2024-04-05 11:06:00 |
Judging History
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]];
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);
for(int i=0;i<n;++i)for(int j=1;j<=m;++j)scanf("%d",&a[i][j]);
for(int S=0;S<pw[n];++S)for(int i=0;i<n;++i)st[S][i]=S/pw[i]%3;
for(int S=0;S<pw[n];++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<pw[n];++S)chk[i][S]=checkS(i,S);
for(int S=0;S<pw[n];++S)for(int T=0;T<pw[n];++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<pw[n];++S)if(chk[m][S])g[m][S][0]=1;
for(int i=m;i>1;--i)for(int S=0;S<pw[n];++S)if(chk[i][S])
for(int j=0;j+i<n+m;++j)if(g[i][S][j])
for(int T=0;T<pw[n];++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<pw[n];++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<pw[n];++S)if(chk[1][S])f[1][S][0][pmx[S]]=1;
for(int i=1;i<m;++i)for(int S=0;S<pw[n];++S)if(chk[i][S]){
vector<int>tmp;
for(int T=0;T<pw[n];++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];
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<pw[n];++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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5836kb
input:
2 2 1 0 3 2
output:
1 2
result:
ok single line: '1 2'
Test #2:
score: 0
Accepted
time: 4ms
memory: 9064kb
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: -100
Wrong Answer
time: 23ms
memory: 18880kb
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:
101778607 62263736
result:
wrong answer 1st lines differ - expected: '988900801 3995091', found: '101778607 62263736'