QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#353008 | #7989. 三染色 | ucup-team1004 | AC ✓ | 138ms | 23376kb | C++14 | 3.0kb | 2024-03-13 19:38:20 | 2024-03-13 19:38:20 |
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];
void add(int &x,int 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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5828kb
input:
2 2 1 0 3 2
output:
1 2
result:
ok single line: '1 2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 7256kb
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: 28ms
memory: 17208kb
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: 138ms
memory: 23376kb
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: 91ms
memory: 21856kb
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: 32ms
memory: 17184kb
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: 35ms
memory: 18340kb
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: 9ms
memory: 14284kb
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: 82ms
memory: 21932kb
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: 37ms
memory: 18500kb
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: 3ms
memory: 12584kb
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: 22ms
memory: 18148kb
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: 7ms
memory: 13272kb
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: 3ms
memory: 14472kb
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: 2ms
memory: 8848kb
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: 70ms
memory: 20960kb
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: 107ms
memory: 22276kb
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: 77ms
memory: 21648kb
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: 132ms
memory: 23216kb
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: 120ms
memory: 23244kb
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: 3ms
memory: 6320kb
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: 46ms
memory: 16068kb
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'