QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#353022 | #7989. 三染色 | ucup-team1004 | WA | 1ms | 3764kb | C++14 | 3.0kb | 2024-03-13 19:49:36 | 2024-03-13 19:49:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) (a).begin(),(a).end()
#ifdef DEBUG
template<class T>
ostream& operator << (ostream &out,vector<T> a){
out<<'[';
for(T x:a)out<<x<<',';
return out<<']';
}
template<class T>
vector<T> ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
const int N=5,M=51,K=pow(3,N)+3,mod=998244353;
const int w[3][3]={{0,-1,1},{1,0,-1},{-1,1,0}};
int n,m,a[N][M];
int v[K][N],is[M][K],ok[K][K],mx[K],cur[K];
bool chk(int a,int b,int c,int d){
return !((1<<a|1<<b|1<<c|1<<d)==7&&(a==b||b==c||c==d||d==a));
}
int f[M][K][M+N][N+1],g[M][K][M+N];
#define add(x,y) ((x)+=(y)>=mod&&((x)-=mod))
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=1;j<=m;j++)cin>>a[i][j];
}
int U=pow(3,n)-0.5;
for(int S=0;S<=U;S++){
for(int i=0,x=S;i<n;i++){
v[S][i]=x%3,x/=3;
}
}
for(int j=1;j<=m;j++){
for(int S=0;S<=U;S++){
is[j][S]=1;
for(int i=0;i<n;i++){
if(a[i][j]!=3&&a[i][j]!=v[S][i])is[j][S]=0;
}
}
}
for(int S=0;S<=U;S++){
mx[S]=cur[S]=0;
for(int i=1,x=0;i<n;i++){
x+=w[v[S][i-1]][v[S][i]];
if(x>mx[S])mx[S]=x,cur[S]=i;
}
}
for(int S=0;S<=U;S++){
for(int T=0;T<=U;T++){
ok[S][T]=1;
for(int i=0;i+1<n;i++){
if(!chk(v[S][i],v[T][i],v[T][i+1],v[S][i+1]))ok[S][T]=0;
}
}
}
for(int S=0;S<=U;S++)if(is[m][S]){
g[m][S][0]=1;
}
for(int i=m;i>1;i--){
for(int S=0;S<=U;S++)if(is[i][S]){
for(int p=0;p<m-i+n;p++){
if(!g[i][S][p])continue;
for(int T=0;T<=U;T++)if(is[i-1][T]&&ok[T][S]){
int q=p+mx[S]-w[v[S][0]][v[T][0]]-mx[T];
add(g[i-1][T][max(q,0)],g[i][S][p]);
}
}
}
}
for(int i=1;i<=m;i++){
for(int S=0;S<=U;S++){
for(int p=1;p<m-i+n;p++){
add(g[i][S][p],g[i][S][p-1]);
}
}
}
for(int S=0;S<=U;S++)if(is[1][S]){
f[1][S][0][cur[S]]=1;
}
int ans1=0,ans2=0;
for(int i=1;i<m;i++){
int lim=i-1+n;
for(int S=0;S<=U;S++)if(is[i][S]){
vector<int>pos;
for(int T=0;T<=U;T++){
if(is[i+1][T]&&ok[S][T])pos.push_back(T);
}
for(int p=0;p<lim;p++){
add(f[i][S][p+1][n],f[i][S][p][0]);
int cnt=1ll*f[i][S][p][0]*g[i][S][p]%mod;
add(ans1,cnt);
ans2=(ans2+1ll*cnt*(i-1))%mod;
for(int d=1;d<=n;d++){
if(!f[i][S][p][d])continue;
int t=d<n?d-1:n;
for(int T:pos){
int q=p+mx[S]-w[v[S][0]][v[T][0]]-mx[T];
if(q>0){
add(f[i+1][T][q][t],f[i][S][p][d]);
}else if(q==0){
add(f[i+1][T][q][min(t,cur[T])],f[i][S][p][d]);
}else{
add(f[i+1][T][0][cur[T]],f[i][S][p][d]);
}
}
}
}
}
}
for(int S=0;S<=U;S++){
int lim=n+m-1;
for(int p=0;p<lim;p++){
for(int d=0;d<n;d++){
add(ans1,f[m][S][p][d]);
ans2=(ans2+1ll*(m-1+d)*f[m][S][p][d])%mod;
}
}
}
cout<<ans1<<' '<<ans2<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3764kb
input:
2 2 1 0 3 2
output:
0 0
result:
wrong answer 1st lines differ - expected: '1 2', found: '0 0'