QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#351016 | #7858. Basic Equation Solving | ushg8877 | AC ✓ | 1667ms | 3916kb | C++14 | 3.3kb | 2024-03-11 12:07:05 | 2024-03-20 11:12:45 |
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<<11|10],le[26],ri[26],Le[1<<11|15],Ri[1<<11|15];
int f[11][1<<11|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;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
1 P=NP
output:
766136394
result:
ok single line: '766136394'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 2000CNY>3000USD
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3692kb
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: 3576kb
input:
2 BC>DD BD<EA
output:
27271695
result:
ok single line: '27271695'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
3 CE>ED CC>BA BB<AC
output:
426829091
result:
ok single line: '426829091'
Test #6:
score: 0
Accepted
time: 17ms
memory: 3676kb
input:
10 KG<EI EJ>DA EB<IH EB>JG KF<CF JC>FC IC<BJ FI>HH KD>AH AE>GJ
output:
87744507
result:
ok single line: '87744507'
Test #7:
score: 0
Accepted
time: 43ms
memory: 3676kb
input:
10 EK<GM EL<DC DH>IH EF>BL IM<LL EH<JA DJ<AL GL>MB DB>FM AI<HA
output:
665533468
result:
ok single line: '665533468'
Test #8:
score: 0
Accepted
time: 110ms
memory: 3916kb
input:
10 OD<FK FJ>NL NH>KB KM>CA CI>JH CI<AH CE>GI CO<EG FA>HA FA<IJ
output:
878923575
result:
ok single line: '878923575'
Test #9:
score: 0
Accepted
time: 1667ms
memory: 3736kb
input:
10 YH>UQ UQ>FD YZ>MK FY<GO YV<QW UV<VJ UZ>EB EQ>LX VP>ZF LZ>TS
output:
867624189
result:
ok single line: '867624189'
Test #10:
score: 0
Accepted
time: 1661ms
memory: 3684kb
input:
10 YH<UL UD<FY FK<MU MM<GO GG<QW QJ<VQ VZ<EB EG<LX LZ<ZP ZV<TS
output:
57935948
result:
ok single line: '57935948'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
6 EDDC>AB5A B<C E9A9B>CACAA DE2>A0D DBCDAC>AED3D5 AAA>BB5
output:
169889581
result:
ok single line: '169889581'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
9 C<B A>B FDF2<FBDB DB>B4 CF>DA EF4<D1A B8<A5 B3>BF FFA<D5B
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
5 SP6<GCT J0RFZ<ZZLUX UDY7<UEVX C1CQ>FXTG SOCT07<MEABU8
output:
603602671
result:
ok single line: '603602671'
Test #14:
score: 0
Accepted
time: 3ms
memory: 3692kb
input:
7 F>M G8F<KC5 F06<E8G H5J<BJE M8CDE<DIGMC AE08>EFI7 DM>CI
output:
821791712
result:
ok single line: '821791712'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
10 PS1>O9O G76>F8S J<S SB>Y4 WS<VM E<N ZR<CV G8T>XPJ J<A KT<LS
output:
97272892
result:
ok single line: '97272892'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
4 K1TVV0>TOB4QTH E5U5C9>QGDEGU Q9LW3SK>LWFRP DXUQM=V4N4
output:
467745652
result:
ok single line: '467745652'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
5 BC5F<AC3F FA4<D48306EDD EFDD>FDABE CF5C<AFDDB FAF<C387
output:
808992671
result:
ok single line: '808992671'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
1 ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY
output:
835948861
result:
ok single line: '835948861'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
3 A=A 00109=109 XX=Z
output:
276262510
result:
ok single line: '276262510'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
2 ABCDEFGHIJKL=CDEFGHIJKLMN OPQRSTUVWXYZ=RSTUVWXYZOPQ
output:
100000
result:
ok single line: '100000'
Test #21:
score: 0
Accepted
time: 5ms
memory: 3628kb
input:
9 N=A8 TT<QO3G LS>JV TSG>U5F D<A934 FK<HKG O>S1 GT<BBCX SG>S
output:
929594610
result:
ok single line: '929594610'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
0
output:
673653469
result:
ok single line: '673653469'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 AB<CD AC<BD AD<BC
output:
219041723
result:
ok single line: '219041723'
Extra Test:
score: 0
Extra Test Passed