QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#354269 | #7858. Basic Equation Solving | ucup-team1198# | AC ✓ | 151ms | 3852kb | C++20 | 7.2kb | 2024-03-15 02:15:03 | 2024-10-14 18:03:09 |
Judging History
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,我给组数据试试?
詳細信息
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