QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351015#7858. Basic Equation Solvingushg8877RE 0ms3680kbC++143.3kb2024-03-11 12:06:152024-03-11 12:06:15

Judging History

This is the latest submission verdict.

  • [2024-03-20 11:12:17]
  • hack成功,自动添加数据
  • (/hack/581)
  • [2024-03-11 12:06:15]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 3680kb
  • [2024-03-11 12:06:15]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
const int MOD=998244353;
int n,d[10];string a[10],b[10];char op[10];
int fa[26],dsu[26],id[26],ord[26],lk[1<<10|10],le[26],ri[26],Le[1<<10|15],Ri[1<<10|15];
int f[11][1<<10|15];
vector<int> edg[26];// 连边方向:小->大
int ans=0;
inline int find(int *fa,int x){
	while(x^fa[x]) x=fa[x]=fa[fa[x]];
	return x;
}
bool number(char c){return '0'<=c&&c<='9';}
bool letter(char c){return 'A'<=c&&c<='Z';}
void chkmin(int &x,int y){if(x>y)x=y;}
void chkmax(int &x,int y){if(x<y)x=y;}
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
void solve(){
	for(int i=0;i<26;i++) fa[i]=dsu[i]=i,edg[i].clear();
	for(int i=0;i<26;i++) le[i]=0,ri[i]=9;
	for(int i=0;i<n;i++) for(int j=0;j<=d[i];j++) {
		if(letter(a[i][j])&&letter(b[i][j])) fa[find(fa,a[i][j]-'A')]=find(fa,b[i][j]-'A');
		if(op[i]=='='||j<d[i]){
			if(number(a[i][j])&&number(b[i][j])&&a[i][j]!=b[i][j]) return;
			if(number(a[i][j])&&letter(b[i][j])){
				chkmax(le[b[i][j]-'A'],a[i][j]-'0');
				chkmin(ri[b[i][j]-'A'],a[i][j]-'0');
			}if(number(b[i][j])&&letter(a[i][j])){
				chkmax(le[a[i][j]-'A'],b[i][j]-'0');
				chkmin(ri[a[i][j]-'A'],b[i][j]-'0');
			}if(letter(a[i][j])&&letter(b[i][j])) dsu[find(dsu,a[i][j]-'A')]=dsu[find(dsu,b[i][j]-'A')];
		}else{
			if(number(a[i][j])&&number(b[i][j])&&a[i][j]>b[i][j]) return;
			if(number(a[i][j])&&letter(b[i][j])) chkmax(le[b[i][j]-'A'],a[i][j]-'0'+1);
			if(number(b[i][j])&&letter(a[i][j])) chkmin(ri[a[i][j]-'A'],b[i][j]-'0'-1);
			if(letter(a[i][j])&&letter(b[i][j])) edg[b[i][j]-'A'].push_back(a[i][j]-'A');
		}
	}
	int prd=1;
	for(int i=0;i<26;i++) if(fa[i]==i){
		vector<int> vec;
		for(int j=0;j<26;j++) if(find(fa,j)==i) vec.push_back(j);
		int n=0;
		for(int j:vec){
			if(dsu[j]==j) ord[n]=j,id[j]=n++;
			else{
				chkmax(le[find(dsu,j)],le[j]);
				chkmin(ri[find(dsu,j)],ri[j]);
			}
		}
		for(int j=0;j<n;j++) if(ri[j]<le[j]) return;
		for(int j:vec) id[j]=id[find(dsu,j)];
		for(int i=0;i<n;i++) Le[1<<i]=le[ord[i]],Ri[1<<i]=ri[ord[i]];
		for(int i=0;i<(1<<n);i++) lk[i]=0;
		for(int j:vec) for(int k:edg[j]) 
			if(id[j]==id[k]) return; else lk[1<<id[j]]|=1<<id[k];
		for(int S=1;S<(1<<n);S++) if((S&-S)!=S){
			lk[S]=lk[S^(S&-S)]|lk[S&-S];
			Le[S]=max(Le[S^(S&-S)],Le[S&-S]);
			Ri[S]=min(Ri[S^(S&-S)],Ri[S&-S]);
		}
		for(int i=0;i<=10;i++) for(int S=0;S<(1<<n);S++) f[i][S]=0;
		f[0][0]=1;
		for(int i=1;i<=10;i++) for(int S=0;S<(1<<n);S++) {
			f[i][S]=f[i-1][S];
			for(int T=S;T;T=(T-1)&S) if(!(lk[S]&T)&&Le[T]<=i-1&&i-1<=Ri[T]) 
				add(f[i][S],f[i-1][S^T]);
		}
		prd=1ll*prd*f[10][(1<<n)-1]%MOD;
	}
	add(ans,prd);
	return;
}
void dfs(int p){
	if(p==n){
		solve();return;
	}
	if(op[p]=='=') d[p]=a[p].size()-1,dfs(p+1);
	else{
		for(int i=0;i<a[p].size();i++){
			d[p]=i;
			dfs(p+1);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	// freopen("Otomachi_Una.in","r",stdin);
	// freopen("Otomachi_Una.out","w",stdout);
	cin>>n;
	for(int i=0;i<n;i++){
		string p,s,t;
		cin>>p;
		for(int j=0;j<p.size();j++){
			if(p[j]!='<'&&p[j]!='='&&p[j]!='>') t+=p[j];
			else op[i]=p[j],swap(s,t);
		}
		if(op[i]=='>') swap(s,t),op[i]='<';
		while(a[i].size()+s.size()<t.size()) a[i]+='0';
		while(b[i].size()+t.size()<s.size()) b[i]+='0';
		a[i]+=s,b[i]+=t;
	}
	dfs(0);
	cout<<ans<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3592kb

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

4
AB>CD
E<A
BC>FF
EF>F1

output:

23645065

result:

ok single line: '23645065'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

score: -100
Runtime Error

input:

10
KG<EI
EJ>DA
EB<IH
EB>JG
KF<CF
JC>FC
IC<BJ
FI>HH
KD>AH
AE>GJ

output:


result: