QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300752 | #7858. Basic Equation Solving | willow | AC ✓ | 219ms | 3896kb | C++14 | 7.3kb | 2024-01-08 18:54:57 | 2024-01-08 18:54:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int Add(int x, int y) {
return (x += y) >= mod ? x - mod : x;
}
int Sub(int x, int y) {
return (x -= y) < 0 ? x + mod : x;
}
int Mul(int x, int y) {
return 1ll * x * y % mod;
}
string eq[15][2], e;
int n, tot;
struct Dsu {
int fa[26], can[26];
void Init() {
for(int i = 0; i < 26; ++ i)
fa[i] = i, can[i] = (1 << 10) - 1;
}
int Get(int x) {
return x == fa[x] ? x : fa[x] = Get(fa[x]);
}
int Set(int id, int l, int r) {
int p = Get(id), to = 0;
for(int i = l; i <= r; ++ i)
to |= 1 << i;
can[p] &= to;
return can[p];
}
int Merge(int u, int v) {
int x = Get(u), y = Get(v);
if(x == y)
return 1;
fa[y] = x;
can[x] &= can[y];
return can[x];
}
}d;
int ans, clk, to[26][26], deg[26], out[26], ways[26][10], vis[26], id[26];
vector<int> G[26];
queue<int>q;
int ffa[26], compid[26];
int Gget(int x) {
return x == ffa[x] ? x : ffa[x] = Gget(ffa[x]);
}
void Outmerge(int x, int y) {
ffa[Gget(y)] = Gget(x);
}
vector<int> idx[26];
int lesser[26], toid[26], canid[26];
int dp[(1 << 12) + 5][10];
int state_less[(1 << 12) + 5];
int canplace[(1 << 12) + 5];
void Calc(Dsu &now, vector<vector<int> > &less) {
// cerr << "One Calc: ";
// for(int i = 0; i < 26; ++ i) {
// cerr << char(now.Get(i) + 'A') << " ";
// }
// cerr << endl;
// for(int i = 0; i < 26; ++ i) {
// if(now.Get(i) == i) {
// cerr << "letter " << char(i + 'A') << ": ";
// for(int j = 0; j < 10; ++ j)
// cerr << (now.can[i] >> j & 1);
// cerr << endl;
// }
// }
for(int i = 0; i < 26; ++ i)
ffa[i] = i;
++ clk;
for(int i = 0; i < 26; ++ i) {
deg[i] = out[i] = 0;
G[i].clear();
}
// for(int i = 0; i < 26; ++ i)
// if(i != now.Get(i))
// cerr << "Constraint: " << char(i + 'A') << " = " << char(now.Get(i) + 'A') << endl;
for(int i = 0; i < 26; ++ i) {
for(auto v : less[i]) {
int x = now.Get(i), y = now.Get(v);
if(x == y)
return;
if(to[x][y] != clk) {
to[x][y] = clk;
// cerr << "Constraint: " << char(x + 'A') << " < " << char(y + 'A') << endl;
G[x].push_back(y);
Outmerge(x, y);
++ deg[y];
out[x] = 1;
}
}
}
int nowid = 0;
for(int i = 0; i < 26; ++ i) {
if(now.Get(i) != i) {
continue;
}
if(Gget(i) == i) {
idx[nowid].clear();
compid[i] = nowid ++;
}
}
for(int i = 0; i < 26; ++ i) {
if(now.Get(i) != i) {
continue;
}
// cerr << i << " fa = " << Gget(i) << " ";
idx[compid[Gget(i)]].push_back(i);
}
// cerr << endl;
int mul = 1;
for(int i = 0; i < nowid; ++ i) {
int totid = 0;
for(auto x : idx[i]) {
lesser[totid] = 0;
canid[totid] = now.can[x];
toid[x] = totid ++;
// cerr << x << ": ";
// for(auto v : G[x])
// cerr << v << " ";
// cerr << endl;
}
// cerr << endl;
for(auto x : idx[i])
if(!deg[x])
q.push(x);
int sz = 0;
while(!q.empty()) {
int u = q.front();
++ sz;
q.pop();
// cerr << "? " << u << endl;
for(auto v : G[u]) {
lesser[toid[v]] |= lesser[toid[u]] | (1 << toid[u]);
// cerr << u << " -> " << v << endl;
if(!(-- deg[v])) {
q.push(v);
}
}
}
// cerr << sz << endl;
if(sz != (int)idx[i].size())
return;
for(int j = 0; j < 1 << sz; ++ j) {
state_less[j] = 0;
canplace[j] = (1 << 10) - 1;
for(int k = 0; k < sz; ++ k) {
if(j >> k & 1) {
state_less[j] |= lesser[k];
canplace[j] &= canid[k];
}
}
for(int k = 0; k < 10; ++ k) {
dp[j][k] = 0;
}
}
for(int j = 0; j < 1 << sz; ++ j) {
// cerr << j << " " << (state_less[j] & j) << " " << (canplace[j] & 1) << endl;
if(state_less[j] == 0 && (canplace[j] & 1))
dp[j][0] = 1; // , cerr << "! " << j << endl;
}
for(int j = 1; j < 10; ++ j) {
for(int k = 0; k < 1 << sz; ++ k) {
if(dp[k][j - 1]) {
int tmp = (1 << sz) - 1 - k;
for(int st = tmp; ; st = (st - 1) & tmp) {
if(!(canplace[st] >> j & 1))
continue;
if((state_less[st] & st) == 0 && (state_less[st] & k) == state_less[st]) {
// if(idx[i][0] == 0 && idx[i][1] == 2 && idx[i][2] == 5)
// cerr << k << " " << j - 1 << " " << st << " " << endl;
dp[st | k][j] = Add(dp[st | k][j], dp[k][j - 1]);
}
if(!st)
break;
}
}
}
}
mul = Mul(mul, dp[(1 << sz) - 1][9]);
// for(auto x : idx[i])
// cerr << x << " ";
// cerr << endl;
// cerr << "Comp: " << dp[(1 << sz) - 1][9] << endl;
}
// cerr << "Total = " << mul << endl;
ans = Add(ans, mul);
}
void Solve(int pos, Dsu now, vector<vector<int> > less) {
if(pos == tot) {
Calc(now, less);
return;
}
int len = eq[pos][0].length();
for(int i = 0; i < len; ++ i) {
Dsu nxt = now;
if(isdigit(eq[pos][0][i]) && isdigit(eq[pos][1][i])) {
int l = eq[pos][0][i] - '0', r = eq[pos][1][i] - '0';
if(l > r)
break;
if(l < r)
Solve(pos + 1, nxt, less);
if(eq[pos][0][i] != eq[pos][1][i]) {
break;
}
}
if(isdigit(eq[pos][0][i])) {
int l = eq[pos][0][i] - '0', r = eq[pos][1][i] - 'A';
if(nxt.Set(r, l + 1, 9))
Solve(pos + 1, nxt, less);
if(!now.Set(r, l, l))
break;
continue;
}
if(isdigit(eq[pos][1][i])) {
int l = eq[pos][0][i] - 'A', r = eq[pos][1][i] - '0';
if(nxt.Set(l, 0, r - 1))
Solve(pos + 1, nxt, less);
if(!now.Set(l, r, r))
break;
continue;
}
int l = eq[pos][0][i] - 'A', r = eq[pos][1][i] - 'A';
// cerr << eq[pos][0][i] << " < " << eq[pos][1][i] << endl;
less[l].push_back(r);
Solve(pos + 1, nxt, less);
less[l].pop_back();
if(!now.Merge(l, r))
break;
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
d.Init();
for(int i = 1; i <= n; ++ i) {
cin >> e;
string lef = "", rig = "";
int len = e.length(), pos = -1;
for(int j = 0; j < len; ++ j) {
if(e[j] == '=' || e[j] == '>' || e[j] == '<') {
pos = j;
break;
}
}
for(int j = 0; j < pos; ++ j)
lef += e[j];
for(int j = pos + 1; j < len; ++ j)
rig += e[j];
if(e[pos] == '=') {
while(lef.length() < rig.length())
lef = '0' + lef;
while(rig.length() < lef.length())
rig = '0' + rig;
int l = lef.length();
for(int j = 0; j < l; ++ j) {
if(isdigit(lef[j]) && isdigit(rig[j])) {
if(lef[j] != rig[j]) {
return 0 * puts("0");
}
continue;
}
if(isdigit(lef[j])) {
d.Set(rig[j] - 'A', lef[j] - '0', lef[j] - '0');
continue;
}
if(isdigit(rig[j])) {
d.Set(lef[j] - 'A', rig[j] - '0', rig[j] - '0');
continue;
}
d.Merge(lef[j] - 'A', rig[j] - 'A');
}
continue;
}
if(e[pos] == '>') {
swap(lef, rig);
}
if(rig.length() < lef.length()) {
int diff = lef.length() - rig.length();
for(int j = 0; j < diff; ++ j) {
if(!d.Set(lef[j] - 'A', 0, 0)) {
return 0 * puts("0");
}
}
string tmp = "";
for(int j = diff; j < (int)lef.length(); ++ j) {
tmp += lef[j];
}
lef = tmp;
assert(lef.length() == rig.length());
}
else {
while(lef.length() < rig.length()) {
lef = '0' + lef;
}
}
eq[tot][0] = lef;
eq[tot][1] = rig;
// cerr << eq[tot][0] << " < " << eq[tot][1] << endl;
tot ++;
}
Solve(0, d, vector<vector<int> >(26, vector<int>()));
printf("%d\n", ans);
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3728kb
input:
1 P=NP
output:
766136394
result:
ok single line: '766136394'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
1 2000CNY>3000USD
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3804kb
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: 3688kb
input:
2 BC>DD BD<EA
output:
27271695
result:
ok single line: '27271695'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
3 CE>ED CC>BA BB<AC
output:
426829091
result:
ok single line: '426829091'
Test #6:
score: 0
Accepted
time: 3ms
memory: 3792kb
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: 6ms
memory: 3800kb
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: 3796kb
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: 219ms
memory: 3784kb
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: 121ms
memory: 3896kb
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: 3684kb
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: 3760kb
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: 3760kb
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: 3696kb
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: 3692kb
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: 3760kb
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: 3680kb
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: 3788kb
input:
1 ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY
output:
835948861
result:
ok single line: '835948861'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
3 A=A 00109=109 XX=Z
output:
276262510
result:
ok single line: '276262510'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
2 ABCDEFGHIJKL=CDEFGHIJKLMN OPQRSTUVWXYZ=RSTUVWXYZOPQ
output:
100000
result:
ok single line: '100000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3732kb
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: 3636kb
input:
0
output:
673653469
result:
ok single line: '673653469'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
3 AB<CD AC<BD AD<BC
output:
219041723
result:
ok single line: '219041723'
Extra Test:
score: 0
Extra Test Passed