QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#288041 | #7858. Basic Equation Solving | ucup-team1447# | AC ✓ | 510ms | 3892kb | C++14 | 7.7kb | 2023-12-21 16:41:44 | 2024-10-14 18:02:49 |
Judging History
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,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
input:
1 P=NP
output:
766136394
result:
ok single line: '766136394'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
1 2000CNY>3000USD
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
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: 3580kb
input:
2 BC>DD BD<EA
output:
27271695
result:
ok single line: '27271695'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
3 CE>ED CC>BA BB<AC
output:
426829091
result:
ok single line: '426829091'
Test #6:
score: 0
Accepted
time: 14ms
memory: 3608kb
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: 3780kb
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: 46ms
memory: 3604kb
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: 510ms
memory: 3612kb
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: 397ms
memory: 3828kb
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: 6ms
memory: 3876kb
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: 3584kb
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: 3848kb
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: 3580kb
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: 3892kb
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: 3580kb
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: 3548kb
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: 3640kb
input:
1 ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY
output:
835948861
result:
ok single line: '835948861'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
3 A=A 00109=109 XX=Z
output:
276262510
result:
ok single line: '276262510'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
2 ABCDEFGHIJKL=CDEFGHIJKLMN OPQRSTUVWXYZ=RSTUVWXYZOPQ
output:
100000
result:
ok single line: '100000'
Test #21:
score: 0
Accepted
time: 11ms
memory: 3620kb
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: 3824kb
input:
0
output:
673653469
result:
ok single line: '673653469'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
3 AB<CD AC<BD AD<BC
output:
219041723
result:
ok single line: '219041723'
Extra Test:
score: 0
Extra Test Passed