QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#470679#7858. Basic Equation Solvingucup-team052#AC ✓3341ms4064kbC++148.6kb2024-07-10 15:47:392024-07-10 15:47:40

Judging History

你现在查看的是测评时间为 2024-07-10 15:47:40 的历史记录

  • [2024-10-14 18:03:09]
  • 管理员手动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:3329ms
  • 内存:4068kb
  • [2024-07-10 15:47:40]
  • 评测
  • 测评结果:100
  • 用时:3341ms
  • 内存:4064kb
  • [2024-07-10 15:47:39]
  • 提交

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: 3764kb

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3772kb

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: 3764kb

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

score: 0
Accepted
time: 38ms
memory: 4028kb

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: 3744kb

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: 207ms
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: 3319ms
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: 3341ms
memory: 3848kb

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: 3816kb

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: 3696kb

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: 4000kb

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: 3716kb

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: 3760kb

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: 3756kb

input:

4
K1TVV0>TOB4QTH
E5U5C9>QGDEGU
Q9LW3SK>LWFRP
DXUQM=V4N4

output:

467745652

result:

ok single line: '467745652'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3756kb

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: 4036kb

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: 3740kb

input:

2
ABCDEFGHIJKL=CDEFGHIJKLMN
OPQRSTUVWXYZ=RSTUVWXYZOPQ

output:

100000

result:

ok single line: '100000'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3784kb

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: 3904kb

input:

0

output:

673653469

result:

ok single line: '673653469'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

3
AB<CD
AC<BD
AD<BC

output:

219041723

result:

ok single line: '219041723'

Extra Test:

score: 0
Extra Test Passed