QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#426552 | #7858. Basic Equation Solving | lmeowdn | AC ✓ | 2256ms | 4324kb | C++14 | 4.5kb | 2024-05-31 15:04:19 | 2024-05-31 15:04:19 |
Judging History
answer
//Shirasu Azusa 2024.5
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=255,mod=998244353;
int n,m,l[N],r[N],e[N],cnt,w[N],f[11][(1<<12)],te[1<<12],ANS,id[N];
bool g[10][1<<12];
char sen[N];
vi ed[N];
struct node {
int op,len; //-1 < 0 = 1 >
char a[N],b[N];
} p[N];
struct violet {
char x,y; int op;
} q[N],h[N];
void add(int &x,int y) {x=(x+y>=mod?x+y-mod:x+y);}
int calc(vi t) {
static int id[N],pl[N],pr[N]; int m=t.size();
rep(i,0,m-1) id[t[i]]=i, pl[i]=l[t[i]], pr[i]=r[t[i]], e[i]=0;
for(int x:t) for(int y:ed[x]) e[id[x]]|=1<<id[y];
int S=(1<<m)-1;
rep(s,0,S) {
te[s]=0; rep(i,0,m-1) if(s&(1<<i)) te[s]|=e[i];
rep(i,0,9) {
g[i][s]=!(te[s]&s); if(!g[i][s]) continue;
rep(x,0,m-1) if(s&(1<<x)) g[i][s]&=(pl[x]<=i&&i<=pr[x]);
}
} rep(s,0,S) f[0][s]=g[0][s];
rep(i,1,9) rep(s,0,S) f[i][s]=0;
rep(i,1,9) {
rep(s,0,S) if(f[i-1][s]) {
int T=S^s;
for(int t=T;;t=(t-1)&T) if(g[i][t]) {
if(!(te[t]&s)) add(f[i][s|t],f[i-1][s]);
if(!t) break;
}
}
}
//cout<<f[9][S]<<" "<<t.size()<<endl;
return f[9][S];
}
int find(int i) {return i==id[i]?i:id[i]=find(id[i]);}
void work() {
//cout<<"WORK\n";
rep(i,1,128) id[i]=i; rep(i,1,m) h[i]=q[i];
rep(i,1,m) if(h[i].op==0&&isdigit(h[i].y)) swap(h[i].x,h[i].y);
rep(i,1,m) {
if(h[i].op==0) id[find(h[i].x)]=find(h[i].y);
else if(h[i].op==1) swap(h[i].x,h[i].y), h[i].op=-1;
}
rep(x,'0','9') rep(y,x+1,'9') if(find(x)==find(y)) return;
rep(i,1,m) {
if(!isdigit(h[i].x)) h[i].x=find(h[i].x);
if(!isdigit(h[i].y)) h[i].y=find(h[i].y);
}
rep(i,0,25) ed[i].clear(), l[i]=0, r[i]=9, w[i]=0;
rep(c,'A','Z') if(find(c)==c) w[c-'A']=1;
rep(i,0,25) rep(x,'0','9') if(find(i+'A')==find(x)) l[i]=r[i]=x-'0';
rep(i,1,m) if(h[i].op!=0) {
char x=h[i].x, y=h[i].y;
bool dx=isdigit(x), dy=isdigit(y);
if(dx&&dy) {if(x>=y) return;}
else if(dy) {chmin(r[x-'A'],y-'0'-1);}
else if(dx) {chmax(l[y-'A'],x-'0'+1);}
else {ed[x-'A'].eb(y-'A');}
}
rep(i,1,m) if(l[i]>r[i]) return;
rep(i,0,25) id[i]=i;
rep(i,1,m) {
char x=h[i].x, y=h[i].y;
if(!isdigit(x)&&!isdigit(y)) id[find(x-'A')]=find(y-'A');
}
int ans=1;
rep(i,0,25) if(w[i]&&find(i)==i) {
vi tmp; rep(j,0,25) if(w[j]&&find(j)==i) tmp.eb(j);
ans=ans*calc(tmp)%mod;
}
add(ANS,ans);
}
void dfs(int pos) {
if(pos==n+1) {work(); return;}
int cur=m;
if(p[pos].op==0) {
rep(j,0,p[pos].len-1) q[++m]=(violet){p[pos].a[j],p[pos].b[j],0};
dfs(pos+1); m=cur;
} else {
rep(j,0,p[pos].len-1) {
q[++m]=(violet){p[pos].a[j],p[pos].b[j],p[pos].op};
dfs(pos+1);
q[m]=(violet){p[pos].a[j],p[pos].b[j],0};
}
m=cur;
}
}
signed main() {
n=read();
rep(i,1,n) {
scanf("%s",sen); int m=strlen(sen);
int sa=0, sb=0, flag=0;
rep(j,0,m-1) {
if(sen[j]=='=') flag=1, p[i].op=0;
else if(sen[j]=='<') flag=1, p[i].op=-1;
else if(sen[j]=='>') flag=1, p[i].op=1;
else if(!flag) p[i].a[sa++]=sen[j];
else p[i].b[sb++]=sen[j];
}
if(sa<sb) {
per(j,sb-1,sb-sa) p[i].a[j]=p[i].a[j-(sb-sa)];
per(j,sb-sa-1,0) p[i].a[j]='0';
} else if(sa>sb) {
per(j,sa-1,sa-sb) p[i].b[j]=p[i].b[j-(sa-sb)];
per(j,sa-sb-1,0) p[i].b[j]='0';
}
//cout<<p[i].a<<" "<<p[i].b<<" "<<sa<<" "<<sb<<endl;
p[i].len=max(sa,sb);
}
dfs(1);
printf("%lld\n",ANS);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3936kb
input:
1 P=NP
output:
766136394
result:
ok single line: '766136394'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
1 2000CNY>3000USD
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3976kb
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: 4148kb
input:
2 BC>DD BD<EA
output:
27271695
result:
ok single line: '27271695'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
3 CE>ED CC>BA BB<AC
output:
426829091
result:
ok single line: '426829091'
Test #6:
score: 0
Accepted
time: 40ms
memory: 4324kb
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: 86ms
memory: 4112kb
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: 180ms
memory: 4064kb
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: 2137ms
memory: 4300kb
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: 2256ms
memory: 4044kb
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: 3ms
memory: 3920kb
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: 2ms
memory: 4120kb
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: 8ms
memory: 3924kb
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: 5ms
memory: 3868kb
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: 2ms
memory: 3980kb
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: 3892kb
input:
4 K1TVV0>TOB4QTH E5U5C9>QGDEGU Q9LW3SK>LWFRP DXUQM=V4N4
output:
467745652
result:
ok single line: '467745652'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3824kb
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: 3864kb
input:
1 ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY
output:
835948861
result:
ok single line: '835948861'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
3 A=A 00109=109 XX=Z
output:
276262510
result:
ok single line: '276262510'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
2 ABCDEFGHIJKL=CDEFGHIJKLMN OPQRSTUVWXYZ=RSTUVWXYZOPQ
output:
100000
result:
ok single line: '100000'
Test #21:
score: 0
Accepted
time: 6ms
memory: 3932kb
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: 3820kb
input:
0
output:
673653469
result:
ok single line: '673653469'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
3 AB<CD AC<BD AD<BC
output:
219041723
result:
ok single line: '219041723'
Extra Test:
score: 0
Extra Test Passed