QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351015 | #7858. Basic Equation Solving | ushg8877 | RE | 0ms | 3680kb | C++14 | 3.3kb | 2024-03-11 12:06:15 | 2024-03-11 12:06:15 |
Judging History
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