QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#354269#7858. Basic Equation Solvingucup-team1198#AC ✓151ms3852kbC++207.2kb2024-03-15 02:15:032024-10-14 18:03:09

Judging History

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

  • [2024-10-14 18:03:09]
  • 管理员手动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:151ms
  • 内存:3852kb
  • [2024-03-20 11:12:17]
  • hack成功,自动添加数据
  • (/hack/581)
  • [2024-03-15 02:15:04]
  • 评测
  • 测评结果:100
  • 用时:144ms
  • 内存:3888kb
  • [2024-03-15 02:15:03]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int MOD = 998244353;

int add(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}

int sub(int a, int b) {
    return a >= b ? a - b : a + MOD - b;
}

int mul(int a, int b) {
    return (1ll * a * b) % MOD;
}

int pw(int x, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            x = mul(x, x);
            n /= 2;
        } else {
            res = mul(res, x);
            --n;
        }
    }
    return res;
}


const int N = 11;
const int MAXN = 100;
int dp[(1 << N) + 228];

vector<int> G[MAXN];
bool used[MAXN];
vector<int> order;

void dfs(int v) {
    used[v] = true;
    for (int u : G[v]) {
        if (!used[u])
            dfs(u);
    }
    order.emplace_back(v);
}

const int DIGITS = 10;
const int ALPHA = 26;

int solve_g(int n, const vector<int>& should, const vector<pair<int, int>>& edges) {
    /*cerr << n << '\n';
    for (int i = 0; i < n; ++i)
        cerr << should[i] << ' ';
    cerr << '\n';
    for (auto [a, b] : edges)
        cerr << a << '<' << b << ' ';
    cerr << '\n';*/
    // (a, b) means a < b
    fill(used, used + n, false);
    for (auto [a, b] : edges) {
        G[b].emplace_back(a);
    }
    for (int i = 0; i < n; ++i) {
        if (!used[i])
            dfs(i);
    }
    reverse(order.begin(), order.end());
    /*for (int v : order)
        cout << v << ' ';
    cout << '\n';*/
    // edges a -> b
    vector<int> id(n);
    for (int i = 0; i < n; ++i)
        id[order[i]] = i;
    vector<int> mask_less(n);
    vector<int> mask_more(n);
    for (auto [a, b] : edges) {
        mask_more[id[a]] |= 1 << id[b];
        mask_less[id[b]] |= 1 << id[a];
    }
    fill(dp, dp + (1 << n), 0);
    dp[0] = 1;
    for (int digit = 0; digit < DIGITS; ++digit) {
        for (int v = 0; v < n; ++v) {
            if (should[order[v]] != -1 && should[order[v]] != digit)
                continue;
            for (int mask = 0; mask < (1 << n); ++mask) {
                if (mask & (1 << v)) {
                    if ((mask & mask_less[v]) == mask_less[v] && (mask & mask_more[v]) == 0)
                        dp[mask] = add(dp[mask], dp[mask ^ (1 << v)]);
                }
            }
        }
        /*cout << digit << ":\n";
        for (int mask = 0; mask < (1 << n); ++mask)
            cout << dp[mask] << ' ';
        cout << '\n';*/
    }
    for (int i = 0; i < n; ++i)
        G[i].clear();
    order.clear();
    //cerr << "dp: " << dp[(1 << n) - 1] << '\n' << '\n';
    return dp[(1 << n) - 1];
}


int par[DIGITS + ALPHA];

int get(int v) {
    if (par[v] == v)
        return v;
    return par[v] = get(par[v]);
}

bool merge(int v, int u) {
    v = get(v);
    u = get(u);
    if (v == u)
        return false;
    par[v] = u;
    return true;
}

vector<int> G2[MAXN];
bool used2[MAXN];
vector<int> comp;

void dfs2(int v) {
    used2[v] = true;
    comp.emplace_back(v);
    for (int u : G2[v]) {
        if (!used2[u])
            dfs2(u);
    }
}


int solve(const vector<pair<bool, pair<int, int>>>& eqs) {
    // false: a < b
    // true: a = b
    // 0 ... 9 - real numbers
    // 10 ... 35 - letters
    iota(par, par + DIGITS + ALPHA, 0);
    for (auto [type, ab] : eqs) {
        auto [a, b] = ab;
        if (type) {
            merge(a, b);
        }
    }
    for (int i = 0; i < DIGITS; ++i) {
        for (int j = i + 1; j < DIGITS; ++j) {
            if (get(i) == get(j))
                return 0;
        }
    }
    vector<pair<int, int>> edges;
    for (auto [type, ab] : eqs) {
        auto [a, b] = ab;
        a = get(a);
        b = get(b);
        if (!type) {
            edges.emplace_back(a, b);
            G2[a].emplace_back(b);
            G2[b].emplace_back(a);
        }
    }
    fill(used2, used2 + DIGITS + ALPHA, false);
    int ans = 1;
    for (int i = 0; i < DIGITS + ALPHA; ++i) {
        int j = get(i);
        if (used2[j])
            continue;
        dfs2(j);
        map<int, int> new_ids;
        for (int j = 0; j < comp.size(); ++j) {
            new_ids[comp[j]] = j;
        }
        vector<int> should(comp.size(), -1);
        vector<pair<int, int>> cur_edges;
        for (auto [a, b] : edges) {
            if (new_ids.count(a) && new_ids.count(b))
                cur_edges.emplace_back(new_ids[a], new_ids[b]);
        }
        for (int j = 0; j < DIGITS; ++j) {
            int tmp = get(j);
            if (new_ids.count(tmp))
                should[new_ids[tmp]] = j;
        }
        ans = mul(ans, solve_g(comp.size(), should, cur_edges));
        comp.clear();
        if (ans == 0)
            break;
    }
    for (int i = 0; i < DIGITS + ALPHA; ++i)
        G2[i].clear();
    /*for (auto [type, ab] : eqs) {
        auto [a, b] = ab;
        if (type)
            cout << a << '=' << b << ' ';
        else
            cout << a << '<' << b << ' ';
        cout << '\n';
    }
    cerr << "eqs " << ans << '\n';*/
    return ans;
}

vector<pair<bool, pair<int, int>>> eqs;

int get_id(char c) {
    if ('0' <= c && c <= '9')
        return c - '0';
    return c - 'A' + DIGITS;
}

void add_eq(char a, char b) {
    eqs.emplace_back(true, make_pair(get_id(a), get_id(b)));
}

void add_less(char a, char b) {
    eqs.emplace_back(false, make_pair(get_id(a), get_id(b)));
}

int total_ans = 0;

void go_gen(vector<pair<string, string>>& lines, int i) {
    if (i == lines.size()) {
        total_ans = add(total_ans, solve(eqs));
        return;
    }
    int old_sz = eqs.size();
    for (int j = 0; j < lines[i].first.size(); ++j) {
        add_less(lines[i].first[j], lines[i].second[j]);
        go_gen(lines, i + 1);
        eqs.pop_back();
        add_eq(lines[i].first[j], lines[i].second[j]);
    }
    eqs.resize(old_sz);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    vector<pair<string, string>> equal;
    vector<pair<string, string>> need_less;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int j = 0;
        while (s[j] != '=' && s[j] != '<' && s[j] != '>')
            ++j;
        string left = s.substr(0, j);
        string right = s.substr(j + 1, s.size() - j - 1);
        while (left.size() < right.size())
            left = '0' + left;
        while (right.size() < left.size())
            right = '0' + right;
        if (s[j] == '=')
            equal.emplace_back(left, right);
        else if (s[j] == '<')
            need_less.emplace_back(left, right);
        else
            need_less.emplace_back(right, left);
    }
    for (auto [a, b] : equal) {
        for (int i = 0; i < a.size(); ++i)
            add_eq(a[i], b[i]);
    }
    go_gen(need_less, 0);
    cout << total_ans << '\n';
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

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

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

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

input:

4
AB>CD
E<A
BC>FF
EF>F1

output:

23645065

result:

ok single line: '23645065'

Test #4:

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

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

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

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

score: 0
Accepted
time: 10ms
memory: 3652kb

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: 16ms
memory: 3624kb

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: 26ms
memory: 3492kb

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: 151ms
memory: 3492kb

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: 144ms
memory: 3512kb

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

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: 2ms
memory: 3852kb

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: 6ms
memory: 3612kb

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: 3ms
memory: 3552kb

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: 2ms
memory: 3576kb

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

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

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: 1ms
memory: 3548kb

input:

1
ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY

output:

835948861

result:

ok single line: '835948861'

Test #19:

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

input:

3
A=A
00109=109
XX=Z

output:

276262510

result:

ok single line: '276262510'

Test #20:

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

input:

2
ABCDEFGHIJKL=CDEFGHIJKLMN
OPQRSTUVWXYZ=RSTUVWXYZOPQ

output:

100000

result:

ok single line: '100000'

Test #21:

score: 0
Accepted
time: 6ms
memory: 3500kb

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

input:

0

output:

673653469

result:

ok single line: '673653469'

Test #23:

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

input:

3
AB<CD
AC<BD
AD<BC

output:

219041723

result:

ok single line: '219041723'

Extra Test:

score: 0
Extra Test Passed