結果
問題 | No.2428 Returning Shuffle |
ユーザー |
![]() |
提出日時 | 2023-08-18 22:45:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 283 ms / 2,000 ms |
コード長 | 7,599 bytes |
コンパイル時間 | 3,700 ms |
コンパイル使用メモリ | 261,816 KB |
実行使用メモリ | 27,468 KB |
最終ジャッジ日時 | 2024-11-28 08:54:44 |
合計ジャッジ時間 | 6,891 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
// #pragma GCC target("avx")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;#define rep(i,n) for(int i = 0; i < (int)n; i++)#define FOR(n) for(int i = 0; i < (int)n; i++)#define repi(i,a,b) for(int i = (int)a; i < (int)b; i++)#define all(x) x.begin(),x.end()//#define mp make_pair#define vi vector<int>#define vvi vector<vi>#define vvvi vector<vvi>#define vvvvi vector<vvvi>#define pii pair<int,int>#define vpii vector<pair<int,int>>template<typename T>void chmax(T &a, const T &b) {a = (a > b? a : b);}template<typename T>void chmin(T &a, const T &b) {a = (a < b? a : b);}using ll = long long;using ld = long double;using ull = unsigned long long;const ll INF = numeric_limits<long long>::max() / 2;const ld pi = 3.1415926535897932384626433832795028;const ll mod = 998244353;int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};#define int long longtemplate<long long MOD>struct Modular_Int {long long x;Modular_Int() = default;Modular_Int(long long x_) : x(x_ >= 0? x_%MOD : (MOD-(-x_)%MOD)%MOD) {}long long val() const {return (x%MOD+MOD)%MOD;}long long get_mod() const {return MOD;}Modular_Int<MOD>& operator^=(long long d) {Modular_Int<MOD> ret(1);long long nx = x;while(d) {if(d&1) ret *= nx;(nx *= nx) %= MOD;d >>= 1;}*this = ret;return *this;}Modular_Int<MOD> operator^(long long d) const {return Modular_Int<MOD>(*this) ^= d;}Modular_Int<MOD> pow(long long d) const {return Modular_Int<MOD>(*this) ^= d;}//use this basicallyModular_Int<MOD> inv() const {return Modular_Int<MOD>(*this) ^ (MOD-2);}//only if the module number is not prime//Don't use. This is broken.// Modular_Int<MOD> inv() const {// long long a = (x%MOD+MOD)%MOD, b = MOD, u = 1, v = 0;// while(b) {// long long t = a/b;// a -= t*b, swap(a, b);// u -= t*v, swap(u, v);// }// return Modular_Int<MOD>(u);// }Modular_Int<MOD>& operator+=(const Modular_Int<MOD> other) {if((x += other.x) >= MOD) x -= MOD;return *this;}Modular_Int<MOD>& operator-=(const Modular_Int<MOD> other) {if((x -= other.x) < 0) x += MOD;return *this;}Modular_Int<MOD>& operator*=(const Modular_Int<MOD> other) {long long z = x;z *= other.x;z %= MOD;x = z;if(x < 0) x += MOD;return *this;}Modular_Int<MOD>& operator/=(const Modular_Int<MOD> other) {return *this = *this * other.inv();}Modular_Int<MOD>& operator++() {x++;if (x == MOD) x = 0;return *this;}Modular_Int<MOD>& operator--() {if (x == 0) x = MOD;x--;return *this;}Modular_Int<MOD> operator+(const Modular_Int<MOD> other) const {return Modular_Int<MOD>(*this) += other;}Modular_Int<MOD> operator-(const Modular_Int<MOD> other) const {return Modular_Int<MOD>(*this) -= other;}Modular_Int<MOD> operator*(const Modular_Int<MOD> other) const {return Modular_Int<MOD>(*this) *= other;}Modular_Int<MOD> operator/(const Modular_Int<MOD> other) const {return Modular_Int<MOD>(*this) /= other;}Modular_Int<MOD>& operator+=(const long long other) {Modular_Int<MOD> other_(other); *this += other_; return *this;}Modular_Int<MOD>& operator-=(const long long other) {Modular_Int<MOD> other_(other); *this -= other_; return *this;}Modular_Int<MOD>& operator*=(const long long other) {Modular_Int<MOD> other_(other); *this *= other_; return *this;}Modular_Int<MOD>& operator/=(const long long other) {Modular_Int<MOD> other_(other); *this /= other_; return *this;}Modular_Int<MOD> operator+(const long long other) const {return Modular_Int<MOD>(*this) += other;}Modular_Int<MOD> operator-(const long long other) const {return Modular_Int<MOD>(*this) -= other;}Modular_Int<MOD> operator*(const long long other) const {return Modular_Int<MOD>(*this) *= other;}Modular_Int<MOD> operator/(const long long other) const {return Modular_Int<MOD>(*this) /= other;}bool operator==(const Modular_Int<MOD> other) const {return (*this).val() == other.val();}bool operator!=(const Modular_Int<MOD> other) const {return (*this).val() != other.val();}bool operator==(const long long other) const {return (*this).val() == other;}bool operator!=(const long long other) const {return (*this).val() != other;}Modular_Int<MOD> operator-() const {return Modular_Int<MOD>(0LL)-Modular_Int<MOD>(*this);}// friend constexpr istream& operator>>(istream& is, mint& x) noexcept {// long long X;// is >> X;// x = X;// return is;// }// friend constexpr ostream& operator<<(ostream& os, mint& x) {// os << x.val();// return os;// }};// const long long MOD_VAL = 1e9+7;const long long MOD_VAL = 998244353;using mint = Modular_Int<MOD_VAL>;struct fast_prime_factorize {private:vector<int> MinFactor;vector<bool> IsPrime;public:vector<int> primes;fast_prime_factorize(const int MAXN) : MinFactor(MAXN), IsPrime(MAXN) {for (int i = 0; i < MAXN; ++i) IsPrime[i] = true, MinFactor[i] = -1;IsPrime[0] = false; IsPrime[1] = false;MinFactor[0] = 0; MinFactor[1] = 1;for (int i = 2; i < MAXN; ++i) {if (IsPrime[i]) {MinFactor[i] = i;primes.push_back(i);for (int j = i*2; j < MAXN; j += i) {IsPrime[j] = false;if (MinFactor[j] == -1) MinFactor[j] = i;}}}}vector<pair<int,int> > factorize(int n) {vector<pair<int,int> > res;while (n != 1) {int prime = MinFactor[n];int exp = 0;while (MinFactor[n] == prime) {++exp;n /= prime;}res.push_back(make_pair(prime, exp));}return res;}bool is_prime(int n) {return IsPrime[n];}vector<int> All_Min_Factor() {return MinFactor;}vector<int> All_Primes() {return primes;}}sieve(1000100);void solve() {int n, m;cin >> n >> m;vi order(n);iota(all(order), 0);// compositionFOR(m) {int t;cin >> t;vi s(t);rep(j, t) {cin >> s[j];--s[j];}int lst = order[s.back()];for(int j = t-1; j > 0; --j) order[s[j]] = order[s[j-1]];order[s[0]] = lst;}// decomposeint circle = 0;vector<bool> done(n, false);auto dfs = [&](int v, auto self) -> void {done[v] = true;++circle;if(!done[order[v]]) {self(order[v], self);}};map<int, int> mp;FOR(n) {if(!done[i]) {circle = 0;dfs(i, dfs);vpii p = sieve.factorize(circle);for(auto e : p) {chmax(mp[e.first], e.second);}}}mint ans = 1;for(auto e : mp) ans *= mint(e.first).pow(e.second);cout << ans.val() << endl;}signed main() {cin.tie(nullptr);ios::sync_with_stdio(false);solve();return 0;}