QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#426552#7858. Basic Equation SolvinglmeowdnAC ✓2256ms4324kbC++144.5kb2024-05-31 15:04:192024-05-31 15:04:19

Judging History

你现在查看的是最新测评结果

  • [2024-05-31 15:04:19]
  • 评测
  • 测评结果:AC
  • 用时:2256ms
  • 内存:4324kb
  • [2024-05-31 15:04:19]
  • 提交

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