QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#470679 | #7858. Basic Equation Solving | ucup-team052# | AC ✓ | 3329ms | 4068kb | C++14 | 8.6kb | 2024-07-10 15:47:39 | 2024-10-14 18:03:09 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
using namespace std;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;
template <typename _T>
inline void read(_T &f) {
f = 0; _T fu = 1; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }
while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
f *= fu;
}
template <typename T>
void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x < 10) putchar(x + 48);
else print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
print(x); putchar(t);
}
const int md = 998244353;
inline int add(int x, int y) {
if (x + y >= md) return x + y - md;
return x + y;
}
inline void addx(int &x, int y) {
x += y;
if (x >= md) x -= md;
}
inline int sub(int x, int y) {
if (x < y) return x - y + md;
return x - y;
}
inline void subx(int &x, int y) {
x -= y;
if (x < 0) x += md;
}
inline int mul(int x, int y) { return 1ull * x * y % md; }
inline int fpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1) ans = mul(ans, x);
y >>= 1; x = mul(x, x);
}
return ans;
}
const int N = 11;
int a[N][55], b[N][55], op[N], len[N];
char c[55];
int n, ans;
int dp[1 << N], ndp[1 << N], sum[1 << N], ok[1 << N], f[26], id[26], L[26], R[26], big[26], vis[26], seq[26];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
int g[26][26][26], e[26][26], l[26][26], r[26][26];
void dfs(int u) {
auto cpy = [&]() {
memcpy(l[u], l[u - 1], sizeof(l[u]));
memcpy(r[u], r[u - 1], sizeof(r[u]));
memcpy(g[u], g[u - 1], sizeof(g[u]));
};
if (u > n) {
cpy();
for (int i = 0; i <= 25; i++) f[i] = i;
for (int i = 0; i <= 25; i++) {
for (int j = i + 1; j <= 25; j++) {
if (g[u][i][j] == 3) {
int x = find(i), y = find(j);
f[x] = f[y] = min(x, y);
}
}
}
int m = 0;
for (int i = 0; i < 26; i++) {
if (find(i) == i) {
id[i] = m;
++m;
}
}
memset(e, 0, sizeof(e));
for (int i = 0; i < m; i++) L[i] = 1, R[i] = 10;
int flag = 1;
for (int i = 0; i <= 25; i++) {
for (int j = 0; j <= 25; j++) {
int x = id[find(i)], y = id[find(j)];
L[x] = max(L[x], l[u][i]);
R[x] = min(R[x], r[u][i]);
if (g[u][i][j] == 1) {
if (x == y) flag = 0;
if (e[x][y] && e[x][y] != 1) flag = 0;
e[x][y] = 1;
}
if (g[u][i][j] == 2) {
if (x == y) flag = 0;
if (e[x][y] && e[x][y] != 2) flag = 0;
e[x][y] = 2;
}
if (g[u][i][j] == 3) {
assert(x == y);
/*
if (e[x][y] && e[x][y] != 3) flag = 0;
e[x][y] = 3;
*/
}
}
}
for (int i = 0; i < m; i++) {
// fprintf(stderr, "L[%d] = %d, R[%d] = %d\n", i, L[i], i, R[i]);
if (L[i] > R[i]) {
flag = 0;
break;
}
}
if (!flag) return;
memset(vis, 0, sizeof(vis));
int res = 1;
for (int i = 0; i < m; i++) {
if (vis[i]) continue;
queue <int> q; q.push(i); vis[i] = 1;
int len = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
seq[len] = u; ++len;
for (int j = 0; j < m; j++) {
if (!vis[j] && e[u][j]) {
vis[j] = 1; q.push(j);
}
}
}
for (int j = 0; j < len; j++) {
big[j] = 0;
for (int k = 0; k < len; k++) {
if (e[seq[j]][seq[k]] == 1) {
big[j] |= (1 << k);
}
}
}
for (int j = 0; j < (1 << len); j++) {
sum[j] = 0;
for (int k = 0; k < len; k++) {
if ((j >> k) & 1) {
sum[j] |= big[k];
}
}
}
memset(dp, 0, (1 << len) * 4);
dp[0] = 1;
for (int num = 1; num <= 10; num++) {
memset(ndp, 0, (1 << len) * 4);
for (int j = 0; j < (1 << len); j++) {
ok[j] = 1;
for (int k = 0; k < len; k++) {
if ((j >> k) & 1) {
if (num < L[seq[k]] || R[seq[k]] < num) {
ok[j] = 0;
break;
}
}
}
}
for (int j = 0; j < (1 << len); j++) {
for (int s = j; ; s = (s - 1) & j) {
if (ok[s]) {
if ((sum[s] & (j ^ s)) == sum[s]) ndp[j] = add(ndp[j], dp[j ^ s]);
}
if (!s) break;
}
}
memcpy(dp, ndp, (1 << len) * 4);
}
res = mul(res, dp[(1 << len) - 1]);
}
ans = add(ans, res);
return;
}
auto addeq = [&](int x, int y) {
if (x < 0 && y < 0) return x == y;
if (x < 0 && y >= 0) swap(x, y);
if (x >= 0 && y < 0) {
l[u][x] = max(l[u][x], -y), r[u][x] = min(r[u][x], -y);
return l[u][x] <= r[u][x];
}
if (g[u][x][y] && g[u][x][y] != 3) {
return false;
}
g[u][x][y] = g[u][y][x] = 3;
return true;
};
auto add1 = [&](int x, int y) {
if (x < 0 && y < 0) return -x > -y;
if (x < 0 && y >= 0) {
r[u][y] = min(r[u][y], -x - 1);
return l[u][y] <= r[u][y];
}
if (x >= 0 && y < 0) {
l[u][x] = max(l[u][x], -y + 1);
return l[u][x] <= r[u][x];
}
if (g[u][x][y] && g[u][x][y] != 1) {
return false;
}
g[u][x][y] = 1; g[u][y][x] = 2;
return true;
};
if (op[u] == 1) {
for (int i = 1; i <= len[u]; i++) {
cpy();
int flag = 1;
for (int j = i + 1; j <= len[u]; j++) {
if (!addeq(a[u][j], b[u][j])) {
flag = 0;
break;
}
}
if (!add1(a[u][i], b[u][i])) flag = 0;
if (flag) dfs(u + 1);
}
}
if (op[u] == 3) {
cpy();
for (int i = 1; i <= len[u]; i++) {
if (!addeq(a[u][i], b[u][i])) {
return;
}
}
dfs(u + 1);
}
}
int main() {
read(n);
for (int i = 0; i <= 25; i++) l[0][i] = 1, r[0][i] = 10;
for (int i = 1; i <= n; i++) {
scanf("%s", c + 1);
int len = strlen(c + 1), lena = 0, lenb = 0;
for (int j = 1; j <= len; j++) {
if ((c[j] >= 'A' && c[j] <= 'Z') || (c[j] >= '0' && c[j] <= '9')) {
if (!op[i]) {
++lena;
if (c[j] >= 'A' && c[j] <= 'Z') a[i][lena] = c[j] - 'A';
else a[i][lena] = -(c[j] - '0') - 1;
} else {
++lenb;
if (c[j] >= 'A' && c[j] <= 'Z') b[i][lenb] = c[j] - 'A';
else b[i][lenb] = -(c[j] - '0') - 1;
}
} else {
if (c[j] == '>') op[i] = 1;
if (c[j] == '<') op[i] = 2;
if (c[j] == '=') op[i] = 3;
}
}
reverse(a[i] + 1, a[i] + lena + 1);
reverse(b[i] + 1, b[i] + lenb + 1);
while (lena < lenb) {
++lena;
a[i][lena] = -1;
}
while (lenb < lena) {
++lenb;
b[i][lenb] = -1;
}
::len[i] = lena;
if (op[i] == 2) {
op[i] = 1;
for (int j = 1; j <= lena; j++) swap(a[i][j], b[i][j]);
}
}
dfs(1);
print(ans, '\n');
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3688kb
input:
1 P=NP
output:
766136394
result:
ok single line: '766136394'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
1 2000CNY>3000USD
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3968kb
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: 3684kb
input:
2 BC>DD BD<EA
output:
27271695
result:
ok single line: '27271695'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
3 CE>ED CC>BA BB<AC
output:
426829091
result:
ok single line: '426829091'
Test #6:
score: 0
Accepted
time: 38ms
memory: 3672kb
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: 83ms
memory: 3748kb
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: 205ms
memory: 3848kb
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: 3313ms
memory: 3676kb
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: 3329ms
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: 1ms
memory: 3720kb
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: 4036kb
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: 7ms
memory: 4012kb
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: 3816kb
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: 3704kb
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: 3716kb
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: 3772kb
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: 3764kb
input:
1 ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY
output:
835948861
result:
ok single line: '835948861'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
3 A=A 00109=109 XX=Z
output:
276262510
result:
ok single line: '276262510'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
2 ABCDEFGHIJKL=CDEFGHIJKLMN OPQRSTUVWXYZ=RSTUVWXYZOPQ
output:
100000
result:
ok single line: '100000'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3764kb
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: 3900kb
input:
0
output:
673653469
result:
ok single line: '673653469'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
3 AB<CD AC<BD AD<BC
output:
219041723
result:
ok single line: '219041723'
Extra Test:
score: 0
Extra Test Passed