QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288038 | #7858. Basic Equation Solving | ucup-team1447# | WA | 1ms | 3624kb | C++14 | 7.7kb | 2023-12-21 16:34:09 | 2023-12-21 16:34:09 |
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;
}
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'