QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#269147 | #7858. Basic Equation Solving | ucup-team1209# | AC ✓ | 113ms | 4100kb | C++20 | 4.5kb | 2023-11-29 13:24:54 | 2024-10-14 18:02:47 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin, std::cout;
using ll = long long;
int n;
const int N = 26;
const int mod = 998244353;
using u64 = unsigned long long;
std::string l[N], r[N];
int op[N];
int m;
const int M = 11;
int edge[1 << M];
int dp[1 << M];
int mask[1 << M];
int min[M], max[M];
void inc(int & x, int y) {
if((x += y) >= mod) {
x -= mod;
}
}
int solve(int n) {
memset(mask, 0, 4 << n);
memset(dp, 0, 4 << n);
for(int i = 0;i < 1 << n;++i) {
for(int j = 0;j < n;++j) if((i >> j & 1) == 0) {
if((edge[j] & i) == edge[j]) {
mask[i] |= 1 << j;
}
}
}
dp[0] = 1;
for(int i = 0;i <= 9;++i) {
int valid = 0;
for(int j = 0;j < n;++j) if(min[j] <= i && i <= max[j]) {
valid |= 1 << j;
}
for(int j = (1 << n) - 1;j >= 0;--j) if(int v = dp[j]) {
int add = valid & mask[j];
for(int k = add;k;k = (k - 1) & add) {
inc(dp[j | k], v);
}
}
}
memset(edge, 0, n << 2);
return dp[(1 << n) - 1];
}
struct graph {
int l[N], r[N];
int gt[N][N];
int eq[N][N];
int col[N];
int colpb[N];
int le[N], ri[N];
int G[N][N];
void lim(int x, int L, int R) {
l[x] = std::max(l[x], L);
r[x] = std::min(r[x], R);
}
void init() {
for(int i = 0;i < N;++i) {
l[i] = 0, r[i] = 9;
le[i] = 0, ri[i] = 9;
col[i] = -1;
colpb[i] = -1;
}
}
int solve() {
static std::queue<int> Q;
int cc = 0;
for(int i = 0;i < N;++i) if(col[i] == -1) {
col[i] = cc; Q.push(i);
for(;Q.size();) {
int x = Q.front(); Q.pop();
for(int j = 0;j < N;++j) if(eq[x][j] && col[j] == -1) {
col[j] = cc; Q.push(j);
}
}
++cc;
}
for(int i = 0;i < N;++i) {
le[col[i]] = std::max(le[col[i]], l[i]);
ri[col[i]] = std::min(ri[col[i]], r[i]);
for(int j = 0;j < N;++j) if(gt[i][j]) {
G[col[i]][col[j]] = 1;
}
}
for(int i = 0;i < cc;++i) col[i] = -1;
int res = 1;
for(int i = 0;i < cc;++i) if(col[i] == -1) {
static std::vector<int> con;
col[i] = 0; Q.push(i); con = {i};
for(;Q.size();) {
int x = Q.front(); Q.pop();
for(int j = 0;j < cc;++j) if((G[x][j] || G[j][x]) && col[j] == -1) {
col[j] = 0; Q.push(j);
con.push_back(j);
}
}
int m = con.size();
for(int i = 0;i < m;++i) {
min[i] = le[con[i]];
max[i] = ri[con[i]];
for(int j = 0;j < m;++j) {
edge[i] |= G[con[i]][con[j]] << j;
}
}
res = (u64) res * ::solve(m) % mod;
}
return res;
}
} G;
int ans;
void dfs0(int x, graph t) {
if(x == m) {
inc(ans, t.solve());
return ;
}
for(int lcp = 0;lcp < (int) l[x].size();++lcp) {
graph z = t;
int bad = 0;
for(int j = 0;j < lcp;++j) {
int a = isalpha(l[x][j]);
int b = isalpha(r[x][j]);
if(a && b) {
z.eq[l[x][j] - 'A'][r[x][j] - 'A'] = 1;
z.eq[r[x][j] - 'A'][l[x][j] - 'A'] = 1;
}
if(!a && !b) {
if(l[x][j] != r[x][j]) {
bad = 1;
break;
}
}
char A = l[x][j], B = r[x][j];
if(a && !b) z.lim(A - 'A', B - '0', B - '0');
if(!a && b) z.lim(B - 'A', A - '0', A - '0');
}
if(bad) continue;
int a = isalpha(l[x][lcp]);
int b = isalpha(r[x][lcp]);
if(!a && !b) {
if(l[x][lcp] <= r[x][lcp]) {
continue;
}
} else if(a && b) {
z.gt[l[x][lcp] - 'A'][r[x][lcp] - 'A'] = 1;
} else if(a && !b) {
z.lim(l[x][lcp] - 'A', r[x][lcp] - '0' + 1, 9);
} else if(!a && b) {
z.lim(r[x][lcp] - 'A', 0, l[x][lcp] - '0' - 1);
}
dfs0(x + 1, z);
}
}
int main() {
std::ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
G.init();
for(int i = 0;i < n;++i) {
std::string s, l, r;
char op;
cin >> s;
for(int i = 0;i < (int) s.size();++i) {
if(s[i] == '=' || s[i] == '<' || s[i] == '>') {
op = s[i];
l = std::string(s.begin(), s.begin() + i);
r = std::string(s.begin() + i + 1, s.end());
}
}
for(;l.size() < r.size();) l = "0" + l;
for(;l.size() > r.size();) r = "0" + r;
if(op == '=') {
for(int j = 0;j < (int) l.size();++j) {
int a = isalpha(l[j]);
int b = isalpha(r[j]);
if(a && b) {
G.eq[l[j] - 'A'][r[j] - 'A'] = 1;
G.eq[r[j] - 'A'][l[j] - 'A'] = 1;
}
if(!a && !b) {
if(l[j] != r[j]) {
puts("0");
return 0;
}
}
if(b) std::swap(l[j], r[j]), std::swap(a, b);
if(a && !b) {
G.lim(l[j] - 'A', r[j] - '0', r[j] - '0');
}
}
} else {
if(op == '<') op = '>', std::swap(l, r);
::l[m] = l;
::r[m] = r;
::op[m++] = op;
}
}
dfs0(0, G);
cout << ans << '\n';
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
input:
1 P=NP
output:
766136394
result:
ok single line: '766136394'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
1 2000CNY>3000USD
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3664kb
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: 3796kb
input:
2 BC>DD BD<EA
output:
27271695
result:
ok single line: '27271695'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
3 CE>ED CC>BA BB<AC
output:
426829091
result:
ok single line: '426829091'
Test #6:
score: 0
Accepted
time: 9ms
memory: 3908kb
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: 13ms
memory: 4100kb
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: 21ms
memory: 3908kb
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: 113ms
memory: 3904kb
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: 111ms
memory: 4068kb
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: 4ms
memory: 4056kb
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: 3816kb
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: 3816kb
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: 4ms
memory: 4004kb
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: 3872kb
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: 3600kb
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: 3752kb
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: 3936kb
input:
1 ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY
output:
835948861
result:
ok single line: '835948861'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
3 A=A 00109=109 XX=Z
output:
276262510
result:
ok single line: '276262510'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
2 ABCDEFGHIJKL=CDEFGHIJKLMN OPQRSTUVWXYZ=RSTUVWXYZOPQ
output:
100000
result:
ok single line: '100000'
Test #21:
score: 0
Accepted
time: 8ms
memory: 3800kb
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: 3936kb
input:
3 AB<CD AC<BD AD<BC
output:
219041723
result:
ok single line: '219041723'
Extra Test:
score: 0
Extra Test Passed