QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#847179#7989. 三染色nullptr_qwqAC ✓156ms5032kbC++143.2kb2025-01-07 18:33:142025-01-07 18:33:14

Judging History

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

  • [2025-01-07 18:33:14]
  • 评测
  • 测评结果:AC
  • 用时:156ms
  • 内存:5032kb
  • [2025-01-07 18:33:14]
  • 提交

answer

// Problem: P10042 [CCPC 2023 北京市赛] 三染色
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10042
// Memory Limit: 512 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=500005;
inline int qpow(int x,ll y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)res=1ll*res*x%mod; return res; }
inline void inc(int &x,const int y){ x=(x+y>=mod)?(x+y-mod):(x+y); }
inline void dec(int &x,const int y){ x=(x>=y)?(x-y):(x+mod-y); }
inline void mul(int &x,const int y){ x=1ll*x*y%mod; }
inline int add(const int x,const int y){ return (x+y>=mod)?(x+y-mod):(x+y); }
inline int sub(const int x,const int y){ return (x>=y)?(x-y):(x+mod-y); }
inline int prod(const int x,const int y){ return 1ll*x*y%mod; }
const int MR=58,NR=250,TR=5,pw[NR]={1,3,9,27,81,243},mat[MR][MR]={{0,1,-1},{-1,0,1},{1,-1,0}};
int n,m,a[MR][TR],chk[MR][NR],st[NR][TR];
vector<int>tr[NR];
int check_transfer(int s,int t){
	F(i,1,n-1){
		const int x=st[s][i-1],y=st[t][i-1],z=st[t][i],w=st[s][i];
		if(mat[x][y]+mat[y][z]+mat[z][w]+mat[w][x]!=0)return 0;
	}
	return 1;
}
int mnv[NR],mnp[NR],f[2][NR][MR][TR],g[2][NR][MR][TR];
void solve(){
	cin>>n>>m; const int mx=pw[n]-1;
	F(j,0,n-1)F(i,1,m)cin>>a[i][j];
	F(s,0,mx)F(i,0,n-1)st[s][i]=(s/pw[i])%3;
	F(i,1,m)F(s,0,mx)chk[i][s]=1;
	F(i,1,m)F(s,0,mx)F(j,0,n-1)if(a[i][j]<3&&a[i][j]!=st[s][j])chk[i][s]=0;
	F(s,0,mx)F(t,0,mx)if(check_transfer(s,t))tr[s].push_back(t);
	F(s,0,mx){
		int cnt=0;
		F(i,1,n-1){
			cnt+=mat[st[s][i-1]][st[s][i]];
			if(cnt<mnv[s])mnv[s]=cnt,mnp[s]=i;
		} mnv[s]*=-1;
	}
	F(s,0,mx)if(chk[1][s])f[1][s][mnv[s]][mnp[s]]=1,g[1][s][mnv[s]][mnp[s]]=mnp[s];
	F(i,2,m){
		const int cur=i&1,lst=cur^1; memset(f[cur],0,sizeof f[cur]),memset(g[cur],0,sizeof g[cur]);
		F(s,0,mx)F(j,0,i+n-1)F(k,0,n-1)for(int t:tr[s])if(chk[i][t]){
			const int val=f[lst][s][j][k]; if(!val)continue;
			const int l=mat[t%3][s%3]-j+mnv[t];
			if(l<0||(l==0&&k-1<=mnp[t])){
				const int qwq=j-mat[t%3][s%3];
				inc(f[cur][t][qwq][max(0,k-1)],val);
				inc(g[cur][t][qwq][max(0,k-1)],g[lst][s][j][k]);
			} else inc(f[cur][t][mnv[t]][mnp[t]],val),inc(g[cur][t][mnv[t]][mnp[t]],1ll*val*(i+mnp[t]-1)%mod);
		}
	} int ans1=0,ans2=0;
	F(s,0,mx)F(j,0,m+n)F(k,0,n-1)inc(ans1,f[m&1][s][j][k]),inc(ans2,g[m&1][s][j][k]);
	cout<<ans1<<' '<<ans2;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int zsy=1;
	F(____,1,zsy)solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4340kb

input:

2 2
1 0
3 2

output:

1 2

result:

ok single line: '1 2'

Test #2:

score: 0
Accepted
time: 4ms
memory: 4920kb

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: 89ms
memory: 4896kb

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: 155ms
memory: 4960kb

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: 123ms
memory: 4904kb

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: 83ms
memory: 4976kb

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: 84ms
memory: 4952kb

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: 66ms
memory: 4944kb

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: 122ms
memory: 4964kb

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: 89ms
memory: 4900kb

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: 64ms
memory: 4896kb

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: 79ms
memory: 4980kb

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: 71ms
memory: 4968kb

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: 67ms
memory: 4908kb

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: 4928kb

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: 119ms
memory: 4904kb

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: 140ms
memory: 4980kb

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: 116ms
memory: 4980kb

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: 156ms
memory: 5032kb

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: 155ms
memory: 5024kb

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: 4ms
memory: 4916kb

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: 57ms
memory: 4956kb

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'