QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288041#7858. Basic Equation Solvingucup-team1447#AC ✓565ms3580kbC++147.7kb2023-12-21 16:41:442023-12-21 16:41:44

Judging History

你现在查看的是测评时间为 2023-12-21 16:41:44 的历史记录

  • [2024-10-14 18:02:49]
  • 管理员手动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:510ms
  • 内存:3892kb
  • [2024-03-20 11:12:17]
  • hack成功,自动添加数据
  • (/hack/581)
  • [2023-12-21 16:41:44]
  • 评测
  • 测评结果:100
  • 用时:565ms
  • 内存:3580kb
  • [2023-12-21 16:41:44]
  • 提交

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

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3464kb

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

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

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

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

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

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

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

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

score: 0
Accepted
time: 14ms
memory: 3496kb

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: 25ms
memory: 3528kb

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: 54ms
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: 565ms
memory: 3496kb

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: 436ms
memory: 3488kb

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: 5ms
memory: 3464kb

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

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

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: 4ms
memory: 3468kb

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

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

input:

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

output:

467745652

result:

ok single line: '467745652'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3460kb

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

input:

1
ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY

output:

835948861

result:

ok single line: '835948861'

Test #19:

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

input:

3
A=A
00109=109
XX=Z

output:

276262510

result:

ok single line: '276262510'

Test #20:

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

input:

2
ABCDEFGHIJKL=CDEFGHIJKLMN
OPQRSTUVWXYZ=RSTUVWXYZOPQ

output:

100000

result:

ok single line: '100000'

Test #21:

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

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

input:

0

output:

673653469

result:

ok single line: '673653469'

Test #23:

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

input:

3
AB<CD
AC<BD
AD<BC

output:

219041723

result:

ok single line: '219041723'

Extra Test:

score: 0
Extra Test Passed