QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288038#7858. Basic Equation Solvingucup-team1447#WA 1ms3624kbC++147.7kb2023-12-21 16:34:092023-12-21 16:34:09

Judging History

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

  • [2024-03-20 11:12:17]
  • hack成功,自动添加数据
  • (/hack/581)
  • [2023-12-21 16:34:09]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3624kb
  • [2023-12-21 16:34:09]
  • 提交

answer

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
void myassert(bool con)
{
    if (!con)
        std::cout << 0 << std::endl, exit(0);
}
const int MOD = 998244353;
struct mint
{
    unsigned v;
    mint(unsigned v_ = 0) : v(v_) {}
    mint operator-() const { return v ? MOD - v : *this; }
    mint &operator+=(const mint &X) { return (v += X.v) >= MOD ? v -= MOD : v, *this; }
    mint &operator-=(const mint &X) { return (v += MOD - X.v) >= MOD ? v -= MOD : v, *this; }
    mint &operator*=(const mint &X) { return v = 1llu * v * X.v % MOD, *this; }
    mint &operator/=(const mint &X) { return *this *= X.inv(); }
    mint pow(long long B) const
    {
        B %= MOD - 1;
        if (B < 0)
            B += MOD - 1;
        mint res = 1, A = *this;
        while (B)
        {
            if (B & 1)
                res *= A;
            B >>= 1;
            A *= A;
        }
        return res;
    }
    mint inv() const { return pow(MOD - 2); }
    friend mint operator+(const mint &A, const mint &B) { return mint(A) += B; }
    friend mint operator-(const mint &A, const mint &B) { return mint(A) -= B; }
    friend mint operator*(const mint &A, const mint &B) { return mint(A) *= B; }
    friend mint operator/(const mint &A, const mint &B) { return mint(A) /= B; }
    friend std::istream &operator>>(std::istream &A, mint &B) { return A >> B.v; }
    friend std::ostream &operator<<(std::ostream &A, const mint &B) { return A << B.v; }
    friend bool operator==(const mint &A, const mint &B) { return A.v == B.v; }
    explicit operator bool() const { return v; }
} ans;
int n;
struct dsu
{
    int fa[26];
    dsu() { std::iota(fa, fa + 26, 0); }
    int find(int now) { return fa[now] == now ? now : fa[now] = find(fa[now]); }
    void merge(int A, int B) { fa[find(A)] = find(B); }
};
void set(char A, char B, std::array<int, 26> &able, dsu &d, bool &ok)
{
    if (A > B)
        std::swap(A, B);
    if (B <= '9')
        ok &= A == B;
    else if (A >= 'A')
        d.merge(A - 'A', B - 'A');
    else
        for (int k = 0; k != 10; ++k)
            if (k + '0' != A)
                able[B - 'A'] &= ~(1 << k);
}
std::string l[10], r[10], m[10];
void dfs(int now, mint v, std::array<int, 26> able, dsu d, bool ok, std::vector<std::pair<int, int>> e)
{
    if (!ok)
        return;
    if (now == n)
    {
        for (int i = 0; i != 26; ++i)
            able[d.find(i)] &= able[i];
        dsu t = d;
        for (auto i : e)
            t.merge(i.first, i.second);
        mint val = 1;
        for (int i = 0; i != 26; ++i)
            if (t.find(i) == i)
            {
                std::vector<int> g;
                for (int j = 0; j != 26; ++j)
                    if (d.find(j) == j && t.find(j) == i)
                        g.push_back(j);
                int need[1 << g.size()];
                std::fill(need, need + (1 << g.size()), 0);
                for (auto j : e)
                {
                    std::size_t A = std::find(g.begin(), g.end(), d.find(j.first)) - g.begin(),
                                B = std::find(g.begin(), g.end(), d.find(j.second)) - g.begin();
                    if (A != g.size() && B != g.size())
                        need[1 << B] |= 1 << A;
                }
                for (std::size_t j = 0; j != g.size(); ++j)
                    for (int k = 0; k != 1 << g.size(); ++k)
                        if (k >> j & 1)
                            need[k] |= need[k ^ 1 << j];
                mint dp[1 << g.size()];
                dp[0] = 1;
                for (int j = 0; j != 10; ++j)
                {
                    mint tmp[1 << g.size()];
                    int v = 0;
                    for (std::size_t k = 0; k != g.size(); ++k)
                        v |= (able[g[k]] >> j & 1) << k;
                    if (g.size() == 2)
                        std::cout << std::bitset<26>(v) << std::endl;
                    for (std::size_t k = v; k; k = (k - 1) & v)
                    {
                        if (k & need[k])
                            continue;
                        for (int l = 1 << g.size(); l--;)
                        {
                            l &= ~k & ~need[k];
                            tmp[l | k | need[k]] += dp[l | need[k]];
                        }
                    }
                    for (int k = 0; k != 1 << g.size(); ++k)
                        dp[k] += tmp[k];
                    if (g.size() == 2)
                    {
                        std::cout << g[1] << std::endl;
                        for (int k = 0; k != 1 << g.size(); ++k)
                            std::cout << dp[k] << ' ';
                        std::cout << std::endl;
                    }
                }
                val *= dp[(1 << g.size()) - 1];
            }
        ans += v * val;
        return;
    }
    for (std::size_t i = 0; i != l[now].size(); ++i)
    {
        std::array<int, 26> nable = able;
        dsu nd = d;
        bool nok = ok;
        std::vector<std::pair<int, int>> ne = e;
        for (std::size_t j = i; ++j != l[now].size();)
            set(l[now][j], r[now][j], nable, nd, nok);
        for (std::size_t j = l[now].size(); j != r[now].size(); ++j)
            set('0', r[now][j], nable, nd, nok);
        char L = l[now][i], R = r[now][i];
        if (L <= '9' && R <= '9')
            nok &= L < R;
        else if (L >= 'A' && R <= '9')
        {
            for (int j = 0; j != 10; ++j)
                if (!(j + '0' < R))
                    nable[L - 'A'] &= ~(1 << j);
        }
        else if (L <= '9' && R >= 'A')
        {
            for (int j = 0; j != 10; ++j)
                if (!(L < j + '0'))
                    nable[R - 'A'] &= ~(1 << j);
        }
        else if (L >= 'A' && R >= 'A')
            ne.push_back({L - 'A', R - 'A'});
        dfs(now + 1, v, nable, nd, nok, ne);
    }
    if (l[now].size() < r[now].size())
    {
        dfs(now + 1, v, able, d, ok, e);
        for (std::size_t i = l[now].size(); i != r[now].size(); ++i)
            set('0', r[now][i], able, d, ok);
        dfs(now + 1, -v, able, d, ok, e);
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    std::array<int, 26> init1;
    init1.fill((1 << 10) - 1);
    dsu init2;
    bool init3 = true;
    for (int i = 0; i != n; ++i)
    {
        static std::string s;
        std::cin >> s;
        l[i].clear();
        m[i].clear();
        r[i].clear();
        for (auto j : s)
            switch (j)
            {
            case '<':
            case '=':
            case '>':
                m[i].push_back(j);
                break;
            default:
                if (m[i].empty())
                    l[i].push_back(j);
                else
                    r[i].push_back(j);
                break;
            }
        if (m[i] == ">")
            m[i] = "<", std::swap(l[i], r[i]);
        std::reverse(l[i].begin(), l[i].end());
        std::reverse(r[i].begin(), r[i].end());
        if (m[i] == "=")
        {
            while (l[i].size() < r[i].size())
                l[i].push_back('0');
            while (r[i].size() < l[i].size())
                r[i].push_back('0');
            for (std::size_t j = 0; j != l[i].size(); ++j)
                set(l[i][j], r[i][j], init1, init2, init3);
            --i;
            --n;
            continue;
        }
        while (r[i].size() < l[i].size())
            r[i].push_back('0');
    }
    dfs(0, 1, init1, init2, init3, std::vector<std::pair<int, int>>());
    std::cout << ans << std::endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

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

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

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

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

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3624kb

input:

3
CE>ED
CC>BA
BB<AC

output:

00000000000000000000000011
4
1 1 0 0 
00000000000000000000000011
4
1 2 0 0 
00000000000000000000000011
4
1 3 0 0 
00000000000000000000000011
4
1 4 0 0 
00000000000000000000000011
4
1 5 0 0 
00000000000000000000000011
4
1 6 0 0 
00000000000000000000000011
4
1 7 0 0 
00000000000000000000000011
4
1 8 0...

result:

wrong answer 1st lines differ - expected: '426829091', found: '00000000000000000000000011'