QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#294130 | #7858. Basic Equation Solving | hos_lyric | AC ✓ | 425ms | 4140kb | C++14 | 8.5kb | 2023-12-30 08:15:12 | 2024-03-20 11:12:33 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;
int root(vector<int> &uf, int u) {
return (uf[u] < 0) ? u : (uf[u] = root(uf, uf[u]));
}
bool connect(vector<int> &uf, int u, int v) {
u = root(uf, u);
v = root(uf, v);
if (u == v) return false;
if (uf[u] > uf[v]) swap(u, v);
uf[u] += uf[v];
uf[v] = u;
return true;
}
constexpr int A = 10;
constexpr int B = 26;
Mint solveConnected(int n, const vector<int> &cs, const vector<pair<int, int>> &es) {
// if(!(n==1&&cs==vector<int>{1023}&&es.empty()))cerr<<COLOR("93")<<n<<" "<<cs<<" "<<es<<COLOR()<<endl;
vector<int> cands(1 << n);
for (int p = 0; p < 1 << n; ++p) {
cands[p] = ((1 << n) - 1) - p;
for (const auto &e : es) if (!(p & 1 << e.first)) {
cands[p] &= ~(1 << e.second);
}
}
vector<Mint> dp(1 << n, 0);
dp[0] = 1;
for (int a = 0; a < A; ++a) {
int q0 = 0;
for (int u = 0; u < n; ++u) if (cs[u] >> a & 1) {
q0 |= 1 << u;
}
for (int p = 1 << n; --p >= 0; ) {
const int sup = q0 & cands[p];
for (int q = sup; q; --q &= sup) {
dp[p + q] += dp[p];
}
}
}
return dp.back();
}
int N;
char S[20][60];
vector<char> O;
vector<string> X, Y;
vector<int> poss;
Mint solve() {
// cerr<<COLOR("33")<<poss<<COLOR()<<endl;
vector<int> uf(B, -1);
vector<int> can(B, (1 << A) - 1);
vector<pair<int, int>> edges;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < poss[i]; ++j) {
const int x = X[i][j];
const int y = Y[i][j];
if (isdigit(x)) {
if (isdigit(y)) {
if (!(x == y)) {
return 0;
}
} else {
can[y - 'A'] &= (1 << (x - '0'));
}
} else {
if (isdigit(y)) {
can[x - 'A'] &= (1 << (y - '0'));
} else {
connect(uf, x - 'A', y - 'A');
}
}
}
if (O[i] == '<') {
const int x = X[i][poss[i]];
const int y = Y[i][poss[i]];
if (isdigit(x)) {
if (isdigit(y)) {
if (!(x < y)) {
return 0;
}
} else {
// (x, A)
can[y - 'A'] &= ((1 << A) - (1 << ((x - '0') + 1)));
}
} else {
if (isdigit(y)) {
// [0, y)
can[x - 'A'] &= ((1 << (y - '0')) - 1);
} else {
edges.emplace_back(x - 'A', y - 'A');
}
}
}
}
// cerr<<"uf = "<<uf<<endl;
// cerr<<"can = "<<can<<endl;
// cerr<<"edges = "<<edges<<endl;
int C = 0;
vector<int> ids(B, -1);
for (int b = 0; b < B; ++b) if (uf[b] < 0) {
ids[b] = C++;
}
vector<int> ands(C, (1 << A) - 1);
for (int b = 0; b < B; ++b) {
ids[b] = ids[root(uf, b)];
ands[ids[b]] &= can[b];
}
vector<int> UF(C, -1);
for (const auto &edge : edges) {
const int u = ids[edge.first];
const int v = ids[edge.second];
if (u == v) {
return 0;
}
connect(UF, u, v);
}
vector<vector<int>> uss(C);
for (int c = 0; c < C; ++c) {
uss[root(UF, c)].push_back(c);
}
vector<vector<pair<int, int>>> ess(C);
for (const auto &edge : edges) {
const int u = ids[edge.first];
const int v = ids[edge.second];
ess[root(UF, u)].emplace_back(u, v);
}
vector<int> IDS(C, -1);
Mint ret = 1;
for (int c = 0; c < C; ++c) if (UF[c] < 0) {
const auto &us = uss[c];
auto &es = ess[c];
const int usLen = us.size();
vector<int> cs(usLen);
for (int x = 0; x < usLen; ++x) {
IDS[us[x]] = x;
cs[x] = ands[us[x]];
}
for (auto &e : es) {
e.first = IDS[e.first];
e.second = IDS[e.second];
}
ret *= solveConnected(usLen, cs, es);
}
return ret;
}
Mint rec(int i) {
Mint ret = 0;
if (i == N) {
ret += solve();
} else if (O[i] == '=') {
poss[i] = X[i].size();
ret += rec(i + 1);
} else {
for (int &j = poss[i] = 0; j < (int)X[i].size(); ++j) {
ret += rec(i + 1);
}
}
return ret;
}
int main() {
for (; ~scanf("%d", &N); ) {
for (int i = 0; i < N; ++i) {
scanf("%s", S[i]);
}
O.assign(N, '?');
X.assign(N, "");
Y.assign(N, "");
for (int i = 0; i < N; ++i) {
for (int j = 0; ; ++j) {
if (~string("<>=").find(S[i][j])) {
O[i] = S[i][j];
X[i] = string(S[i], S[i] + j);
Y[i] = S[i] + (j + 1);
break;
}
}
if (O[i] == '>') {
O[i] = '<';
swap(X[i], Y[i]);
}
if (X[i].size() < Y[i].size()) X[i] = string(Y[i].size() - X[i].size(), '0') + X[i];
if (X[i].size() > Y[i].size()) Y[i] = string(X[i].size() - Y[i].size(), '0') + Y[i];
}
cerr<<"O = "<<O<<endl;
cerr<<"X = "<<X<<endl;
cerr<<"Y = "<<Y<<endl;
poss.assign(N, -1);
const Mint ans = rec(0);
printf("%u\n", ans.x);
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4112kb
input:
1 P=NP
output:
766136394
result:
ok single line: '766136394'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
1 2000CNY>3000USD
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4084kb
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: 3824kb
input:
2 BC>DD BD<EA
output:
27271695
result:
ok single line: '27271695'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
3 CE>ED CC>BA BB<AC
output:
426829091
result:
ok single line: '426829091'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3808kb
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: 14ms
memory: 4140kb
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: 30ms
memory: 3880kb
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: 425ms
memory: 3932kb
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: 329ms
memory: 3788kb
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: 3912kb
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: 1ms
memory: 3840kb
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: 4ms
memory: 3836kb
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: 2ms
memory: 3788kb
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: 3844kb
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: 4092kb
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: 3868kb
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: 4136kb
input:
1 ABCDEFGHIJKLMNOPQRSTUVWX>BCDEFGHIJKLMNOPQRSTUVWXY
output:
835948861
result:
ok single line: '835948861'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
3 A=A 00109=109 XX=Z
output:
276262510
result:
ok single line: '276262510'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
2 ABCDEFGHIJKL=CDEFGHIJKLMN OPQRSTUVWXYZ=RSTUVWXYZOPQ
output:
100000
result:
ok single line: '100000'
Test #21:
score: 0
Accepted
time: 9ms
memory: 3828kb
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: 4112kb
input:
0
output:
673653469
result:
ok single line: '673653469'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
3 AB<CD AC<BD AD<BC
output:
219041723
result:
ok single line: '219041723'
Extra Test:
score: 0
Extra Test Passed