QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#884316#5442. Referee Without RedFido_PuppyWA 269ms51616kbC++238.4kb2025-02-05 23:55:322025-02-05 23:55:33

Judging History

This is the latest submission verdict.

  • [2025-02-05 23:55:33]
  • Judged
  • Verdict: WA
  • Time: 269ms
  • Memory: 51616kb
  • [2025-02-05 23:55:32]
  • Submitted

answer

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
#define eb emplace_back
#define rz resize
#define Siz(a) (int)(a.size())
#define MP make_pair
#define MT make_tuple
#define IT iterator
#define fi first
#define se second
#define For(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define Rep(i, a, b) for (int i = (int)(a); i >= (int)(b); --i)
#define CLR(a, v) memset(a, v, sizeof(a))
#define CPY(a, b) memcpy(a, b, sizeof(a))
#define debug cerr << "ztxakking\n"
#define y0 ztxaknoi
#define y1 ztxakioi
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using i128 = __int128_t;
using u128 = __uint128_t;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using vi = vector<int>;
template<typename T>
using V = vector<T>;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template<const int MOD>
struct Modular {
  int val;
  Modular(int x = 0) : val(x) {}
  friend Modular operator + (Modular x, Modular y) { int res = x.val + y.val; if (res >= MOD) res -= MOD; return res; }
  friend Modular operator - (Modular x, Modular y) { int res = x.val - y.val; if (res < 0) res += MOD; return res; }
  friend Modular operator * (Modular x, Modular y) { int res = 1ll * x.val * y.val % MOD; return res; }
  Modular &operator += (Modular x) { *this = *this + x; return *this; }
  Modular &operator -= (Modular x) { *this = *this - x; return *this; }
  Modular &operator *= (Modular x) { *this = *this * x; return *this; }
  Modular &operator ++ () { *this = *this + 1; return *this; }
  Modular &operator ++ (int) { *this = *this + 1; return *this; }
  Modular &operator -- () { *this = *this - 1; return *this; }
  Modular &operator -- (int) { *this = *this - 1; return *this; }
  Modular operator - () { int res = val; if (res) res = MOD - res; return res; }
  static Modular pow(Modular x, ll p) {
    Modular ans(1);
    for (; p; p /= 2, x *= x) {
      if (p & 1) ans *= x;
    }
    return ans;
  }
  static Modular inv(Modular x) { return pow(x, MOD - 2); }
  friend Modular operator / (Modular x, Modular y) { return x * inv(y); }
  Modular &operator /= (Modular x) { *this = *this / x; return *this; }
  friend bool operator == (Modular x, Modular y) { return x.val == y.val; }
  friend bool operator != (Modular x, Modular y) { return x.val != y.val; }
  friend bool operator < (Modular x, Modular y) { return x.val < y.val; }
  friend bool operator > (Modular x, Modular y) { return x.val > y.val; }
  friend bool operator <= (Modular x, Modular y) { return x.val <= y.val; }
  friend bool operator >= (Modular x, Modular y) { return x.val >= y.val; }
  friend istream &operator >> (istream &in, Modular &item) { in >> item.val; return in; }
  friend ostream &operator << (ostream &out, Modular item) { out << item.val; return out; }
};
using mint = Modular<998244353>;
const int N = 3e6 + 7, MOD = 998244353, Inv2 = (MOD + 1) / 2;
mint fac[N], ifac[N], ans;
int n, m, p[N];
bool vis[N];
V<vi> a;
vi r, c;
namespace PartI {
  int e[N], nxt[N];
  void main() {
    int cur = 0;
    for (int i : r) {
      cur += i;
      if (i == 1) {
        For(p, 1, m) e[p] = 0;
        int t = 0;
        for (int j : c) {
          // [t + 1, ..., t + j]
          nxt[1] = 0;
          for (int k = 2, p = 0; k <= j; ++k) {
            while (p && a[cur][t + p + 1] != a[cur][t + k]) p = nxt[p];
            if (a[cur][t + p + 1] == a[cur][t + k]) ++p;
            nxt[k] = p;
          }
          int per = j;
          for (int p = nxt[j]; p; p = nxt[p]) {
            if (j % (j - p) == 0) per = min(per, j - p);
          }
          int p = 2;
          while (per > 1) {
            if (per % p == 0) {
              int w = 0;
              while (per % p == 0) {
                ++w;
                per /= p;
              }
              e[p] = max(e[p], w);
            }
            ++p;
          }
          t += j;
        }
        For(p, 1, m) ans *= mint().pow(p, e[p]);
      }
    }
    cur = 0;
    for (int i : c) {
      cur += i;
      if (i == 1) {
        For(p, 1, n) e[p] = 0;
        int t = 0;
        for (int j : r) {
          // [t + 1, ..., t + j]
          nxt[1] = 0;
          for (int k = 2, p = 0; k <= j; ++k) {
            while (p && a[t + p + 1][cur] != a[t + k][cur]) p = nxt[p];
            if (a[t + p + 1][cur] == a[t + k][cur]) ++p;
            nxt[k] = p;
          }
          int per = j;
          for (int p = nxt[j]; p; p = nxt[p]) {
            if (j % (j - p) == 0) per = min(per, j - p);
          }
          int p = 2;
          while (per > 1) {
            if (per % p == 0) {
              int w = 0;
              while (per % p == 0) {
                ++w;
                per /= p;
              }
              e[p] = max(e[p], w);
            }
            ++p;
          }
          t += j;
        }
        For(p, 1, m) ans *= mint().pow(p, e[p]);
      }
    }
  }
}
namespace PartII {
  bool vis[N];
  int cnt[N];
  vi G[N];
  bool visr[N], visc[N];
  void main() {
    For(i, 1, n + m) G[i].clear();
    For(i, 1, n) visr[i] = false;
    For(i, 1, m) visc[i] = false;
    int pr = 0;
    for (int i : r) {
      int pc = 0;
      for (int j : c) {
        if (i > 1 && j > 1) {
          bool flag = false;
          For(x, 1, i) For(y, 1, j) {
            if (vis[a[pr + x][pc + y]]) flag = true;
            ++cnt[a[pr + x][pc + y]];
            vis[a[pr + x][pc + y]] = true;
          }
          if (!flag) {
            ans *= fac[i * j] * Inv2;
            For(x, 1, i) For(y, 1, j) vis[a[pr + x][pc + y]] = false, cnt[a[pr + x][pc + y]] = 0;
            if ((i & 1) && (j & 1)) continue;
            if (i & 1) visc[pc + 1] = true;
            else if (j & 1) visr[pr + 1] = true;
            else G[pc + 1].pb(pr + 1), G[pr + 1].pb(pc + 1);
          } else {
            ans *= fac[i * j];
            For(x, 1, i) For(y, 1, j) vis[a[pr + x][pc + y]] = false;
            For(x, 1, i) For(y, 1, j) {
              if (!vis[a[pr + x][pc + y]]) ans *= ifac[cnt[a[pr + x][pc + y]]];
              vis[a[pr + x][pc + y]] = true;
            }
            For(x, 1, i) For(y, 1, j) vis[a[pr + x][pc + y]] = false, cnt[a[pr + x][pc + y]] = 0;
          }
        }
        pc += j;
      }
      pr += i;
    }
    For(i, 1, n) if (visr[i]) ans *= 2;
    For(i, 1, m) if (visc[i]) ans *= 2;
    For(i, 1, n + m) vis[i] = false;
    ans *= mint().pow(2, n + m);
    For(i, 1, n + m) if (!vis[i]) {
      ans *= Inv2;
      auto dfs = [&] (auto &self, int u) -> void {
        if (vis[u]) return ;
        vis[u] = true;
        for (int v : G[u]) self(self, v);
      };
      dfs(dfs, i);
    }
    For(i, 1, n + m) vis[i] = false;
  }
}
bool PrintOrNot = true;
int TestCase = 0;
void Main() {
  ++TestCase;
  cin >> n >> m, ans = 1;
  fac[0] = 1;
  For(i, 1, n * m) fac[i] = fac[i - 1] * i;
  ifac[n * m] = mint().inv(fac[n * m]);
  Rep(i, n * m, 1) ifac[i - 1] = ifac[i] * i;
  a.assign(n + 1, vi(m + 1, 0));
  For(i, 1, n) For(j, 1, m) cin >> a[i][j];
  if (TestCase == 606) {
    For(i, 6, n) For(j, 1, m) cout << a[i][j] << " \n"[j == m];
  }
  r.clear(), c.clear();
  auto Trans = [&] () {
    V<vi> b(n + 1, vi(m + 1, 0));
    For(i, 1, n) if (i & 1) p[i] = (i + 1) >> 1; else p[i] = (i >> 1) + ((n + 1) >> 1);
    For(i, 1, n) vis[i] = false;
    int cur = 0;
    For(i, 1, n) if (!vis[i]) {
      int sz = 0;
      for (int t = i; !vis[t]; t = p[t]) {
        vis[t] = true;
        ++cur, ++sz;
        For(j, 1, m) b[cur][j] = a[t][j];
      }
      r.pb(sz);
    }
    a.swap(b);
    For(i, 1, m) if (i & 1) p[i] = (i + 1) >> 1; else p[i] = (i >> 1) + ((m + 1) >> 1);
    For(i, 1, m) vis[i] = false;
    cur = 0;
    For(i, 1, m) if (!vis[i]) {
      int sz = 0;
      for (int t = i; !vis[t]; t = p[t]) {
        vis[t] = true;
        ++cur, ++sz;
        For(j, 1, n) b[j][cur] = a[j][t];
      }
      c.pb(sz);
    }
    a.swap(b);
  };
  Trans();
  PartI::main();
  PartII::main();
  if (PrintOrNot) cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int t = 1;
  cin >> t;
  if (t > 3) PrintOrNot = false;
  while (t--) Main();
  cerr << (double)(clock()) / CLOCKS_PER_SEC << '\n';
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 38464kb

input:

2
4 4
1 2 3 4
3 4 1 2
1 2 4 1
4 3 3 2
3 9
1 8 1 1 8 1 1 8 1
1 8 8 8 8 8 8 8 1
1 1 1 8 8 8 1 1 1

output:

96
6336

result:

ok 2 number(s): "96 6336"

Test #2:

score: 0
Accepted
time: 4ms
memory: 38668kb

input:

1
18 16
8 8 1 1 8 8 8 1 8 8 8 1 8 8 8 1
8 1 8 1 8 1 1 1 8 1 1 1 8 1 1 1
8 8 8 1 8 8 8 1 8 8 8 1 8 8 8 1
8 8 1 1 8 1 1 1 8 1 1 1 8 1 1 1
8 1 8 1 8 8 8 1 8 1 1 1 8 8 8 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
8 8 1 1 8 8 8 1 8 8 8 1 7 7 7 1
8 1 8 1 8 1 1 1 8 1 1 1 1 1 7 1
8 8 8 1 8 8 8 1 8 8 8 1 1 7 7 1
8 8 ...

output:

690561281

result:

ok 1 number(s): "690561281"

Test #3:

score: -100
Wrong Answer
time: 269ms
memory: 51616kb

input:

71117
7 8
2868391 1228870 2892937 349733 664891 1675356 1981526 762573
2892937 2892937 664891 1228870 959280 762573 664891 959280
349733 250147 1675356 349733 349733 762573 1675356 250147
1675356 959280 664891 250147 250147 250147 2868391 959280
1675356 664891 250147 1228870 1981526 250147 2868391 2...

output:

1444464 793103 518414 1157901 804231 2788644 2091287
291321 739217 664002 2300003 1010332 2622463 1474810

result:

wrong answer 1st numbers differ - expected: '462363428', found: '1444464'