QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#564906 | #7858. Basic Equation Solving | 1234567890# | AC ✓ | 176ms | 3820kb | C++14 | 4.9kb | 2024-09-15 16:57:35 | 2024-10-14 18:03:09 |
Judging History
answer
/*
わんわん……わんだほーいっ☆
Wonderhoy!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
typedef pair<int,int> P;
typedef vector<int> Poly;
typedef vector<P> PolyP;
#define mp make_pair
#define spc putchar(' ')
#define etr putchar('\n')
#define inlp(x,y) putchar(x==y?'\n':' ')
const int MOD=998244353;
inline int Add(int u,int v){return u+v>=MOD?u+v-MOD:u+v;}
inline int Sub(int u,int v){return u-v>=0?u-v:u-v+MOD;}
inline int Mul(int u,int v){return LL(u)*LL(v)%MOD;}
inline int add(int &u,int v){return u=Add(u,v);}
inline int sub(int &u,int v){return u=Sub(u,v);}
inline int mul(int &u,int v){return u=Mul(u,v);}
int QuickPow(int x,int p=MOD-2)
{
int ans=1,base=x;
while(p)
{
if(p&1) mul(ans,base);
mul(base,base);
p>>=1;
}
return ans;
}
int rev[256],idx;
int N;
string s1[55],s2[55];
int equ[55];
Poly eq[55],le[55];
Poly G[55]; // for toposort
Poly leq[55],geq[55]; // for components links (leq/geq only)
Poly lnk[55]; // leq or geq
int deg[55],top[55];
int opt[55]; // -1 for uncertain char
int ans;
int fa[55];
int rid[55];
bool vis[55];
void makeSet(){for(int i=1;i<=idx;++i) fa[i]=i,vis[i]=false,opt[i]=-1,G[i].clear(),leq[i].clear(),geq[i].clear(),lnk[i].clear(),deg[i]=0;}
int findSet(int x){return x==fa[x]?x:fa[x]=findSet(fa[x]);}
void unionSet(int x,int y)
{
x=findSet(x),y=findSet(y);
if(x==y) return ;
fa[y]=x;
}
bool topsort()
{
queue<int> Q;
for(int i=1;i<=idx;++i) if(!deg[i]) Q.push(i);
int ccnt=0;
while(!Q.empty())
{
int u=Q.front();
Q.pop();
top[u]=++ccnt;
for(int v:G[u]) if(!--deg[v]) Q.push(v);
}
return ccnt==idx;
}
int cnt;
int a[55];
void span(int u)
{
if(vis[u]) return ;
vis[u]=true;
if(opt[u]==-1) a[++cnt]=u;
for(int v:lnk[u]) span(v);
}
bool check(int S,int p,int d)
{
p=a[p+1];
int u=findSet(p);
for(int x:leq[u])
{
int v=x;
if(~rid[v])
{
if((S>>rid[v])&1) return false;
}
else if(d>=opt[v]) return false;
}
for(int x:geq[u])
{
int v=x;
if(~rid[v])
{
if(((S>>rid[v])&1)==0) return false;
}
else if(d<=opt[v]) return false;
}
return true;
}
int calc()
{
makeSet();
for(int u=1;u<=idx;++u) for(int v:eq[u]) unionSet(u,v);
for(int i=1;i<=10;++i)
{
int u=findSet(i);
if(~opt[u]) return 0;
opt[u]=i-1;
}
for(int i=1;i<=idx;++i)
{
int u=findSet(i);
if(opt[u]==-1) continue;
for(int p:le[i])
{
int v=findSet(p);
if(opt[v]!=-1 && opt[v]<=opt[u]) return 0;
}
}
for(int i=1;i<=idx;++i)
{
int u=findSet(i);
for(int p:le[i])
{
int v=findSet(p);
if(u==v) return 0;
G[v].push_back(u);
// printf("%d %d\n",u,v);
leq[u].push_back(v),geq[v].push_back(u);
lnk[u].push_back(v),lnk[v].push_back(u);
++deg[u];
}
}
if(!topsort()) return 0;
int ret=1;
for(int p=1;p<=idx;++p)
{
if(findSet(p)!=p || vis[p]) continue;
cnt=0;
span(p);
if(!cnt) continue;
sort(a+1,a+1+cnt,[&](int x,int y){return top[x]<top[y];});
for(int i=1;i<=idx;++i) rid[i]=-1;
for(int i=1;i<=cnt;++i) rid[a[i]]=i-1;
static int f[1<<12];
for(int S=0;S<(1<<cnt);++S) f[S]=0;
f[0]=1;
for(int d=0;d<10;++d)
{
for(int i=0;i<cnt;++i)
{
for(int S=(1<<cnt)-1;~S;--S)
{
if(!f[S]) continue;
if((S>>i)&1) continue;
if(check(S,i,d)) add(f[S|(1<<i)],f[S]);
}
}
}
mul(ret,f[(1<<cnt)-1]);
}
return ret;
}
void dfs(int u)
{
if(u>N) return void(add(ans,calc()));
int len=s1[u].length();
if(equ[u])
{
for(int i=0;i<len;++i)
{
int x=rev[(int)s1[u][i]],y=rev[(int)s2[u][i]];
eq[x].push_back(y),eq[y].push_back(x);
}
dfs(u+1);
for(int i=0;i<len;++i)
{
int x=rev[(int)s1[u][i]],y=rev[(int)s2[u][i]];
eq[x].pop_back(),eq[y].pop_back();
}
}
else
{
for(int i=0;i<len;++i)
{
if(i)
{
int x=rev[(int)s1[u][i-1]],y=rev[(int)s2[u][i-1]];
eq[x].push_back(y),eq[y].push_back(x);
}
int x=rev[(int)s1[u][i]],y=rev[(int)s2[u][i]];
le[x].push_back(y);
dfs(u+1);
le[x].pop_back();
}
for(int i=0;i<len;++i)
{
if(i)
{
int x=rev[(int)s1[u][i-1]],y=rev[(int)s2[u][i-1]];
eq[x].pop_back(),eq[y].pop_back();
}
}
}
}
int main(){
for(int i='0';i<='9';++i) rev[i]=++idx;
for(int i='A';i<='Z';++i) rev[i]=++idx;
cin>>N;
for(int i=1;i<=N;++i)
{
string s;
cin>>s;
int len=int(s.length());
for(int j=0;j<len;++j)
{
if(s[j]=='=' || s[j]=='<' || s[j]=='>')
{
s1[i]=s.substr(0,j),s2[i]=s.substr(j+1,len);
if(s[j]=='>') swap(s1[i],s2[i]);
if(s1[i].length()^s2[i].length())
{
while(s1[i].length()<s2[i].length()) s1[i]="0"+s1[i];
while(s1[i].length()>s2[i].length()) s2[i]="0"+s2[i];
}
// cout<<s1[i]<<" "<<s2[i]<<endl;
equ[i]=int(s[j]=='=');
}
}
}
dfs(1);
cout<<ans<<endl;
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3744kb
input:
1 P=NP
output:
766136394
result:
ok single line: '766136394'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
1 2000CNY>3000USD
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3472kb
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: 3528kb
input:
2 BC>DD BD<EA
output:
27271695
result:
ok single line: '27271695'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 CE>ED CC>BA BB<AC
output:
426829091
result:
ok single line: '426829091'
Test #6:
score: 0
Accepted
time: 3ms
memory: 3568kb
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: 7ms
memory: 3604kb
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: 8ms
memory: 3608kb
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: 176ms
memory: 3596kb
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: 156ms
memory: 3616kb
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: 3600kb
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: 3736kb
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: 0ms
memory: 3820kb
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: 1ms
memory: 3548kb
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: 3552kb
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: 0ms
memory: 3596kb
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: 3812kb
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: 3608kb
input:
1 ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY
output:
835948861
result:
ok single line: '835948861'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
3 A=A 00109=109 XX=Z
output:
276262510
result:
ok single line: '276262510'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 ABCDEFGHIJKL=CDEFGHIJKLMN OPQRSTUVWXYZ=RSTUVWXYZOPQ
output:
100000
result:
ok single line: '100000'
Test #21:
score: 0
Accepted
time: 2ms
memory: 3564kb
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: 3600kb
input:
0
output:
673653469
result:
ok single line: '673653469'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
3 AB<CD AC<BD AD<BC
output:
219041723
result:
ok single line: '219041723'
Extra Test:
score: 0
Extra Test Passed