QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#289606 | #7858. Basic Equation Solving | ucup-team191# | AC ✓ | 82ms | 3916kb | C++23 | 6.2kb | 2023-12-23 19:42:43 | 2023-12-23 19:42:44 |
Judging History
answer
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
const int N=310,MOD=998244353,C=26;
const ll LLINF=1ll<<60;
const char en='\n';
int n,an,par[N],lo[N],hi[N];
bool bio[N];
char ti[N];
string a[N],b[N];
vector<pii> undir,dir;
vi ch[N],rch[N],locha[N],hicha[N];
int add(int a,int b)
{
if (a+b>=MOD) return a+b-MOD;
return a+b;
}
void ad(int&a,int b)
{
a+=b;
if (a>=MOD) a-=MOD;
}
int mul(int a,int b)
{
return a*1ll*b%MOD;
}
int pot(int n,int k)
{
if (k==0) return 1;
int r=pot(n,k/2);
r=mul(r,r);
if (k%2) r=mul(r,n);
return r;
}
int find(int i)
{
if (i==par[i]) return i;
return par[i]=find(par[i]);
}
void mer(int a,int b)
{
a=find(a);
b=find(b);
if (a==b) return;
par[a]=b;
}
vi cucomp;
void dfs1(int i)
{
bio[i]=1;
cucomp.pb(i);
for (auto x: ch[i]) if (!bio[x]) dfs1(x);
for (auto x: rch[i]) if (!bio[x]) dfs1(x);
}
int solveComp(vi lo,vi hi,vi edg)
{
//edg: (edg[i]>>j)&1 if i<j
//topological order
int n=lo.size();
vi dp(1<<n);
dp[0]=1;
for (int col=0;col<10;++col)
{
for (int i=n-1;i>=0;--i) if (col>=lo[i] && col<=hi[i])
{
int subs=(1<<n)-1-edg[i]-(1<<i);
for (int c=subs;c;c=(c-1)&subs) ad(dp[c|(1<<i)],dp[c]);
ad(dp[1<<i],dp[0]);
}
}
return dp[(1<<n)-1];
}
vi redor;
void dfs2(int i)
{
bio[i]=1;
for (auto x: ch[i]) if (!bio[x]) dfs2(x);
redor.pb(i);
}
int solve()
{
//use undir and dir, as well as lo and hi
for (int i=0;i<C;++i)
{
par[i]=i;
ch[i].clear();
rch[i].clear();
bio[i]=0;
lo[i]=0;
hi[i]=9;
for (auto x: locha[i]) lo[i]=max(lo[i],x);
for (auto x: hicha[i]) hi[i]=min(hi[i],x);
//if (i<6) cout<<i<<' '<<lo[i]<<' '<<hi[i]<<endl;
}
/*cout<<"undir:"<<endl;
for (auto x: undir) cout<<x.x<<' '<<x.y<<endl;
cout<<"dir:"<<endl;
for (auto x: dir) cout<<x.x<<' '<<x.y<<endl;*/
for (auto x: undir) mer(x.x,x.y);
//look for connected components
for (auto y: dir)
{
int u=find(y.x),v=find(y.y);
if (u==v) return 0;
ch[u].pb(v);
rch[v].pb(u);
}
vi merlo(C),merhi(C,9);
for (int i=0;i<C;++i)
{
merlo[find(i)]=max(merlo[find(i)],lo[i]);
merhi[find(i)]=min(merhi[find(i)],hi[i]);
}
int an=1;
for (int i=0;i<C;++i) if (par[i]==i && !bio[i])
{
//if (i<8) cout<<"starting comp "<<i<<endl;
cucomp.clear();
dfs1(i);
redor.clear();
for (auto x: cucomp) bio[x]=0;
for (auto x: cucomp) if (!bio[x]) dfs2(x);
reverse(all(redor));
//redor is now topological order
vi lov(redor.size()),hiv(redor.size()),edg(redor.size()),inor(C,-1);
for (int j=0;j<(int)redor.size();++j) inor[redor[j]]=j;
for (int j=0;j<(int)redor.size();++j)
{
lov[j]=merlo[redor[j]];
hiv[j]=merhi[redor[j]];
for (auto x: ch[redor[j]]) if (inor[x]!=-1) edg[j]|=1<<inor[x];
}
/*cout<<i<<endl;
for (auto x: redor) cout<<x<<' ';
cout<<endl;
for (auto x: lov) cout<<x<<' ';
cout<<endl;
for (auto x: hiv) cout<<x<<' ';
cout<<endl;
for (auto x: edg) cout<<x<<' ';
cout<<endl;*/
int musa=solveComp(lov,hiv,edg);
//cout<<musa<<endl<<endl;
an=mul(an,musa);
}
//cout<<an<<endl;
return an;
}
void rek(int d)
{
if (d==n)
{
ad(an,solve());
return;
}
if (ti[d]=='=')
{
while (a[d].size()<b[d].size()) a[d]="0"+a[d];
while (b[d].size()<a[d].size()) b[d]="0"+b[d];
int sz=a[d].size();
for (int i=0;i<sz;++i)
{
if (a[d][i]>='0' && a[d][i]<='9' && b[d][i]>='0' && b[d][i]<='9' && a[d][i]!=b[d][i]) return;
}
for (int i=0;i<sz;++i)
{
if (a[d][i]>='0' && a[d][i]<='9')
{
if (b[d][i]>='A' && b[d][i]<='Z')
{
locha[b[d][i]-'A'].pb(a[d][i]-'0');
hicha[b[d][i]-'A'].pb(a[d][i]-'0');
}
}
else
{
if (b[d][i]>='0' && b[d][i]<='9')
{
locha[a[d][i]-'A'].pb(b[d][i]-'0');
hicha[a[d][i]-'A'].pb(b[d][i]-'0');
}
else
{
undir.pb({a[d][i]-'A',b[d][i]-'A'});
}
}
}
rek(d+1);
for (int i=0;i<sz;++i)
{
if (a[d][i]>='0' && a[d][i]<='9')
{
if (b[d][i]>='A' && b[d][i]<='Z')
{
locha[b[d][i]-'A'].pop_back();
hicha[b[d][i]-'A'].pop_back();
}
}
else
{
if (b[d][i]>='0' && b[d][i]<='9')
{
locha[a[d][i]-'A'].pop_back();
hicha[a[d][i]-'A'].pop_back();
}
else
{
undir.pop_back();
}
}
}
}
if (ti[d]=='>')
{
ti[d]='<';
swap(a[d],b[d]);
}
if (ti[d]=='<')
{
string x=a[d],y=b[d];
while (x.size()<y.size()) x="0"+x;
while (y.size()<x.size()) y="0"+y;
int sz=x.size();
for (int i=0;i<sz;++i)
{
if (x[i]>='0' && x[i]<='9')
{
if (y[i]>='0' && y[i]<='9')
{
if (x[i]<y[i]) rek(d+1);
if (x[i]!=y[i]) break;
}
else
{
locha[y[i]-'A'].pb(x[i]-'0'+1);
rek(d+1);
locha[y[i]-'A'].pop_back();
locha[y[i]-'A'].pb(x[i]-'0');
hicha[y[i]-'A'].pb(x[i]-'0');
}
}
else
{
if (y[i]>='0' && y[i]<='9')
{
hicha[x[i]-'A'].pb(y[i]-'0'-1);
rek(d+1);
hicha[x[i]-'A'].pop_back();
locha[x[i]-'A'].pb(y[i]-'0');
hicha[x[i]-'A'].pb(y[i]-'0');
}
else
{
dir.pb({x[i]-'A',y[i]-'A'});
rek(d+1);
dir.pop_back();
undir.pb({x[i]-'A',y[i]-'A'});
}
}
}
//undo
for (int i=0;i<sz;++i)
{
if (x[i]>='0' && x[i]<='9')
{
if (y[i]>='0' && y[i]<='9')
{
if (x[i]!=y[i]) break;
}
else
{
locha[y[i]-'A'].pop_back();
hicha[y[i]-'A'].pop_back();
}
}
else
{
if (y[i]>='0' && y[i]<='9')
{
locha[x[i]-'A'].pop_back();
hicha[x[i]-'A'].pop_back();
}
else
{
undir.pop_back();
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int inv10=pot(10,MOD-2);
cin>>n;
for (int i=0;i<n;++i)
{
string x;
cin>>x;
for (int j=0;j<(int)x.size();++j) if (x[j]=='<' || x[j]=='=' || x[j]=='>')
{
a[i]=x.substr(0,j);
ti[i]=x[j];
b[i]=x.substr(j+1);
}
}
rek(0);
cout<<an<<en;
//cout<<mul(an,pot(inv10,20))<<en;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
input:
1 P=NP
output:
766136394
result:
ok single line: '766136394'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
1 2000CNY>3000USD
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3644kb
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: 3596kb
input:
2 BC>DD BD<EA
output:
27271695
result:
ok single line: '27271695'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3 CE>ED CC>BA BB<AC
output:
426829091
result:
ok single line: '426829091'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3648kb
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: 5ms
memory: 3656kb
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: 9ms
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: 82ms
memory: 3604kb
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: 82ms
memory: 3608kb
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: 1ms
memory: 3712kb
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: 1ms
memory: 3620kb
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: 3ms
memory: 3596kb
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: 2ms
memory: 3680kb
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: 0ms
memory: 3636kb
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: 3708kb
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: 3640kb
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: 3600kb
input:
1 ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY
output:
835948861
result:
ok single line: '835948861'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3 A=A 00109=109 XX=Z
output:
276262510
result:
ok single line: '276262510'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
2 ABCDEFGHIJKL=CDEFGHIJKLMN OPQRSTUVWXYZ=RSTUVWXYZOPQ
output:
100000
result:
ok single line: '100000'
Test #21:
score: 0
Accepted
time: 9ms
memory: 3704kb
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: 3624kb
input:
0
output:
673653469
result:
ok single line: '673653469'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
3 AB<CD AC<BD AD<BC
output:
219041723
result:
ok single line: '219041723'
Extra Test:
score: 0
Extra Test Passed