結果
問題 | No.2428 Returning Shuffle |
ユーザー |
|
提出日時 | 2023-09-02 09:50:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 261 ms / 2,000 ms |
コード長 | 6,392 bytes |
コンパイル時間 | 1,738 ms |
コンパイル使用メモリ | 139,696 KB |
最終ジャッジ日時 | 2025-02-16 17:58:01 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <cstdint>#include <cstring>#include <ctime>#include <deque>#include <iomanip>#include <iostream>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <unordered_map>#include <unordered_set>using namespace std;template <int mod>struct ModInt {int x;ModInt() : x(0) {}ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p) {if ((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if ((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int)(1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}ModInt &operator^=(long long p) { // quick_pow here:3ModInt res = 1;for (; p; p >>= 1) {if (p & 1) res *= *this;*this *= *this;}return *this = res;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }ModInt operator^(long long p) const { return ModInt(*this) ^= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }explicit operator int() const { return x; } // added by QCFiumModInt operator=(const int p) {x = p;return ModInt(*this);} // added by QCFiumModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;while (b > 0) {t = a / b;a -= t * b;std::swap(a, b);u -= t * v;std::swap(u, v);}return ModInt(u);}friend std::ostream &operator<<(std::ostream &os, const ModInt<mod> &p) {return os << p.x;}friend std::istream &operator>>(std::istream &is, ModInt<mod> &a) {long long x;is >> x;a = ModInt<mod>(x);return (is);}};template <typename T>struct SegmentTree {using Monoid = typename T::Monoid;explicit SegmentTree(int n) : SegmentTree(std::vector<Monoid>(n, T::id())) {}explicit SegmentTree(const std::vector<Monoid> &a) : n(a.size()), sz(1) {while (sz < n) sz <<= 1;data.assign(sz << 1, T::id());std::copy(a.begin(), a.end(), data.begin() + sz);for (int i = sz - 1; i > 0; --i) {data[i] = T::merge(data[i << 1], data[(i << 1) + 1]);}}void set(int idx, const Monoid val) {idx += sz;data[idx] = val;while (idx >>= 1)data[idx] = T::merge(data[idx << 1], data[(idx << 1) + 1]);}Monoid get(int left, int right) const {Monoid res_l = T::id(), res_r = T::id();for (left += sz, right += sz; left < right; left >>= 1, right >>= 1) {if (left & 1) res_l = T::merge(res_l, data[left++]);if (right & 1) res_r = T::merge(data[--right], res_r);}return T::merge(res_l, res_r);}Monoid operator[](const int idx) const { return data[idx + sz]; }private:const int n;int sz; // sz + 原数组坐标 = 线段树里的编号,1 basedstd::vector<Monoid> data;};namespace monoid {template <typename T>struct RangeMinimumQuery {using Monoid = T;static constexpr Monoid id() { return std::numeric_limits<Monoid>::max(); }static Monoid merge(const Monoid &a, const Monoid &b) {return std::min(a, b);}};template <typename T>struct RangeMaximumQuery {using Monoid = T;static constexpr Monoid id() { return std::numeric_limits<Monoid>::lowest(); }static Monoid merge(const Monoid &a, const Monoid &b) {return std::max(a, b);}};template <typename T>struct RangeSumQuery {using Monoid = T;static constexpr Monoid id() { return 0; }static Monoid merge(const Monoid &a, const Monoid &b) { return a + b; }};} // namespace monoidtemplate <typename T>struct DSU {std::vector<T> f, siz;DSU(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }T leader(T x) {while (x != f[x]) x = f[x] = f[f[x]];return x;}bool same(T x, T y) { return leader(x) == leader(y); }bool merge(T x, T y) {x = leader(x);y = leader(y);if (x == y) return false;siz[x] += siz[y];f[y] = x;return true;}T size(int x) { return siz[leader(x)]; }};bool isPrime(long long number) {if (number != 2) {if (number < 2 || number % 2 == 0) {return false;}for (int i = 3; (i * i) <= number; i += 2) {if (number % i == 0) {return false;}}}return true;}std::pair<std::vector<int>, std::vector<int>> get_prime_factor_with_kinds(int n) {std::vector<int> prime_factors;std::vector<int> cnt; // number of i_th factorfor (int i = 2; i <= sqrt(n); i++) {if (n % i == 0) {prime_factors.push_back(i);cnt.push_back(0);while (n % i == 0) n /= i, cnt[(int)prime_factors.size() - 1]++;}}if (n > 1) prime_factors.push_back(n), cnt.push_back(1);assert(prime_factors.size() == cnt.size());return {prime_factors, cnt};}void solve() {int n, m;std::cin >> n >> m;std::vector<int> a(n);std::iota(a.begin(), a.end(), 0);for (int i = 0; i < m; i++) {int k;std::cin >> k;std::vector<int> f(k);for (int &x : f) {std::cin >> x;x--;}// f.push_back(f[0]);for (int j = k - 1; j >= 1; j--) {std::swap(a[f[j]], a[f[j - 1]]);}}DSU<int> dsu(n);std::map<int, int> mp;for (int i = 0; i < n; i++) dsu.merge(i, a[i]);for (int i = 0; i < n; i++) {if (i == dsu.leader(i)) {int sz = dsu.size(i);auto [p, cnt] = get_prime_factor_with_kinds(sz);for (int i = 0; i < p.size(); i++) {mp[p[i]] = std::max(mp[p[i]], cnt[i]);}}}using mint = ModInt<998244353>;mint ans = 1;for (auto [k, v] : mp) {for (int i = 1; i <= v; i++) {ans *= k;}}std::cout << ans << '\n';}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while (t--) solve();return 0;}