QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#470623#7858. Basic Equation Solvingucup-team052#WA 102ms3992kbC++148.8kb2024-07-10 15:29:092024-07-10 15:29:09

Judging History

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

  • [2024-07-10 15:29:09]
  • 评测
  • 测评结果:WA
  • 用时:102ms
  • 内存:3992kb
  • [2024-07-10 15:29:09]
  • 提交

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[N];
int n, ans;

int dp[1 << N], ndp[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[N][26], r[N][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);
                    }
                }
            }
            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]) {
                            int cando = 1;
                            for (int k = 0; k < len; k++) {
                                if ((s >> k) & 1) {
                                    if ((big[k] & (j ^ s)) != big[k]) {
                                        cando = 0;
                                        break;
                                    }
                                }
                            }
                            if (cando) 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);
        return;
    }
}

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3700kb

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

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

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

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

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

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

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

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

score: -100
Wrong Answer
time: 102ms
memory: 3992kb

input:

10
KG<EI
EJ>DA
EB<IH
EB>JG
KF<CF
JC>FC
IC<BJ
FI>HH
KD>AH
AE>GJ

output:

49441396

result:

wrong answer 1st lines differ - expected: '87744507', found: '49441396'