QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#294130#7858. Basic Equation Solvinghos_lyricAC ✓425ms4140kbC++148.5kb2023-12-30 08:15:122024-03-20 11:12:33

Judging History

你现在查看的是最新测评结果

  • [2024-03-20 11:12:33]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:425ms
  • 内存:4140kb
  • [2024-03-20 11:12:17]
  • hack成功,自动添加数据
  • (/hack/581)
  • [2023-12-30 08:15:12]
  • 评测
  • 测评结果:100
  • 用时:418ms
  • 内存:4056kb
  • [2023-12-30 08:15:12]
  • 提交

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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