QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#289544 | #7858. Basic Equation Solving | ucup-team266 | AC ✓ | 35ms | 4028kb | C++14 | 5.9kb | 2023-12-23 18:16:44 | 2024-03-20 11:12:19 |
Judging History
answer
/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest
9. module on time
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
int mask[15][26];
int n;
vector <pair<string,string> > vec;
int ge[15][26][26],gl[15][26][26];
bool Typ(char x)
{
if('0'<=x&&x<='9') return 0;
return 1;
}
int fa[26];
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
x=find(x),y=find(y);
if(x!=y) fa[x]=y;
}
bool cut(int dep)
{
for(int i=0;i<26;i++)
{
if(!mask[dep][i]) return 1;
for(int j=i+1;j<26;j++) if((ge[dep][i][j]>0)+(gl[dep][i][j]>0)+(gl[dep][j][i]>0)>=2) return 1;
}
return 0;
}
int rmask[26];
vector <int> g[26];
int id[26],ok[10];
int adj[1<<11],dp[2][1<<11];
int calc(vector <int> v)
{
int m=v.size();
memset(id,-1,sizeof(id));
memset(ok,0,sizeof(ok));
for(int i=0;i<(1<<m);i++) adj[i]=dp[0][i]=dp[1][i]=0;
for(int i=0;i<v.size();i++)
{
id[v[i]]=i;
for(int j=0;j<10;j++) if(rmask[v[i]]&(1<<j)) ok[j]|=(1<<i);
}
// for(int j=0;j<10;j++) cout<<ok[j]<<" ";
// cout<<"\n";
for(int i=0;i<v.size();i++) for(int j=0;j<g[v[i]].size();j++) assert(id[g[v[i]][j]]!=-1),adj[1<<i]|=(1<<(id[g[v[i]][j]]));
// for(int i=0;i<m;i++) cout<<adj[1<<i]<<" ";
// cout<<"\n";
for(int dim=0;dim<m;dim++) for(int j=0;j<(1<<m);j++) if(j&(1<<dim)) adj[j]|=adj[j^(1<<dim)];
dp[0][(1<<m)-1]=1;
int nw=0;
for(int dig=0;dig<10;dig++)
{
nw^=1;
// assert(ok[dig]==(1<<m)-1);
for(int j=0;j<(1<<m);j++) dp[nw][j]=0;
for(int j=0;j<(1<<m);j++) if(dp[nw^1][j])
{
int S=j&ok[dig]&(((1<<m)-1)^adj[j]);
for(int T=S;;T=(T-1)&S)
{
dp[nw][j^T]=(dp[nw][j^T]+dp[nw^1][j])%mod;
if(!T) break;
}
}
}
// cout<<v.size()<<" "<<v[0]<<" "<<dp[nw][0]<<"\n";
return dp[nw][0];
}
int ans=0;
void calc(int dep)
{
for(int i=0;i<26;i++) fa[i]=i;
for(int i=0;i<26;i++) for(int j=i+1;j<26;j++) if(ge[dep][i][j]||ge[dep][j][i]) merge(i,j);
for(int i=0;i<26;i++) rmask[i]=(find(i)==i?((1<<10)-1):-1);
for(int i=0;i<26;i++) rmask[find(i)]&=mask[dep][i];
for(int i=0;i<26;i++) if(rmask[i]!=-1&&!rmask[i]) return;
int nowans=1;
for(int i=0;i<26;i++) g[i].clear();
int flg=0;
for(int i=0;i<26;i++) for(int j=0;j<26;j++) if(gl[dep][i][j]) flg|=(find(i)==find(j)),g[find(i)].pb(find(j));
for(int i=0;i<26;i++) for(int j=0;j<26;j++) if(gl[dep][i][j]) merge(i,j);
// for(int i=0;i<6;i++) cout<<mask[dep][i]<<" ";
// cout<<"\n";
// for(int i=0;i<6;i++)
// {
// for(int j=0;j<6;j++) cout<<ge[dep][i][j]<<" ";
// cout<<"\n";
// }
// cout<<"\n";
// for(int i=0;i<6;i++)
// {
// for(int j=0;j<6;j++) cout<<gl[dep][i][j]<<" ";
// cout<<"\n";
// }
for(int i=0;i<26;i++) if(find(i)==i)
{
vector <int> v;
for(int j=0;j<26;j++) if(rmask[j]!=-1&&find(j)==i) v.pb(j);//,cout<<j<<" ";
// cout<<"\n";
int x=calc(v);
// cout<<x<<"\n";
nowans=1LL*nowans*x%mod;
}
// system("pause");
ans=(ans+nowans)%mod;
}
void cpy(int dep)
{
for(int i=0;i<26;i++)
{
mask[dep+1][i]=mask[dep][i];
for(int j=0;j<26;j++) ge[dep+1][i][j]=ge[dep][i][j],gl[dep+1][i][j]=gl[dep][i][j];
}
}
void dfs(int dep)
{
if(cut(dep)) return;
if(dep==vec.size())
{
calc(dep);
return;
}
string a=vec[dep].fi,b=vec[dep].se;
for(int s=0;s<a.size();s++)
{
cpy(dep);
for(int i=0;i<s;i++) if(a[i]!=b[i])
{
if(Typ(a[i])==0&&Typ(b[i])==0) return;
if(Typ(a[i])==1&&Typ(b[i])==1) ge[dep+1][a[i]-'A'][b[i]-'A']=ge[dep+1][b[i]-'A'][a[i]-'A']=1;
if(Typ(a[i])==0&&Typ(b[i])==1) mask[dep+1][b[i]-'A']&=(1<<(a[i]-'0'));
if(Typ(a[i])==1&&Typ(b[i])==0) mask[dep+1][a[i]-'A']&=(1<<(b[i]-'0'));
}
if(Typ(a[s])==0&&Typ(b[s])==0)
{
if(a[s]>b[s]) return;
if(a[s]<b[s]) dfs(dep+1);
}
else if(Typ(a[s])==0&&Typ(b[s])==1)
{
for(int j=0;j<=a[s]-'0';j++) if(mask[dep+1][b[s]-'A']&(1<<j)) mask[dep+1][b[s]-'A']^=(1<<j);
dfs(dep+1);
}
else if(Typ(a[s])==1&&Typ(b[s])==0)
{
swap(a[s],b[s]);
for(int j=a[s]-'0';j<=9;j++) if(mask[dep+1][b[s]-'A']&(1<<j)) mask[dep+1][b[s]-'A']^=(1<<j);
swap(a[s],b[s]);
dfs(dep+1);
}
else
{
int u=a[s]-'A',v=b[s]-'A';
if(u!=v)
{
gl[dep+1][u][v]=1;
dfs(dep+1);
// gl[dep+1][u][v]--;
}
}
}
}
void solve()
{
cin>>n;
for(int i=0;i<26;i++) mask[0][i]=(1<<10)-1;
while(n--)
{
string s;
cin>>s;
string a="",b="";
char op;
for(int i=0;i<s.size();i++)
{
if(s[i]=='<'||s[i]=='='||s[i]=='>')
{
op=s[i];
break;
}
a+=s[i];
}
for(int i=s.size()-1;i>=0;i--)
{
if(s[i]=='<'||s[i]=='='||s[i]=='>')
{
op=s[i];
break;
}
b=s[i]+b;
}
while(a.size()<b.size()) a='0'+a;
while(a.size()>b.size()) b='0'+b;
if(op=='=')
{
for(int i=0;i<a.size();i++) if(a[i]!=b[i])
{
if(Typ(a[i])==0&&Typ(b[i])==0)
{
cout<<"0\n";
return;
}
if(Typ(a[i])==1&&Typ(b[i])==1) ge[0][a[i]-'A'][b[i]-'A']=ge[0][b[i]-'A'][a[i]-'A']=1;
if(Typ(a[i])==0&&Typ(b[i])==1) mask[0][b[i]-'A']&=(1<<(a[i]-'0'));
if(Typ(b[i])==0&&Typ(a[i])==1) mask[0][a[i]-'A']&=(1<<(b[i]-'0'));
}
continue;
}
if(op=='>') swap(a,b);
// cout<<a<<" "<<b<<"\n";
vec.pb(mp(a,b));
}
dfs(0);
cout<<ans<<"\n";
}
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3492kb
input:
1 P=NP
output:
766136394
result:
ok single line: '766136394'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
1 2000CNY>3000USD
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3860kb
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: 3608kb
input:
2 BC>DD BD<EA
output:
27271695
result:
ok single line: '27271695'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
3 CE>ED CC>BA BB<AC
output:
426829091
result:
ok single line: '426829091'
Test #6:
score: 0
Accepted
time: 3ms
memory: 3780kb
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: 3ms
memory: 3724kb
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: 5ms
memory: 3660kb
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: 35ms
memory: 3660kb
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: 27ms
memory: 4028kb
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: 3588kb
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: 3716kb
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: 3668kb
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: 3956kb
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: 3924kb
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: 3848kb
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: 3668kb
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: 3532kb
input:
1 ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY
output:
835948861
result:
ok single line: '835948861'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
3 A=A 00109=109 XX=Z
output:
276262510
result:
ok single line: '276262510'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2 ABCDEFGHIJKL=CDEFGHIJKLMN OPQRSTUVWXYZ=RSTUVWXYZOPQ
output:
100000
result:
ok single line: '100000'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3712kb
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: 3508kb
input:
0
output:
673653469
result:
ok single line: '673653469'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
3 AB<CD AC<BD AD<BC
output:
219041723
result:
ok single line: '219041723'
Extra Test:
score: 0
Extra Test Passed