結果
問題 | No.2428 Returning Shuffle |
ユーザー |
![]() |
提出日時 | 2023-08-19 08:03:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 756 ms / 2,000 ms |
コード長 | 1,461 bytes |
コンパイル時間 | 4,132 ms |
コンパイル使用メモリ | 240,120 KB |
実行使用メモリ | 198,548 KB |
最終ジャッジ日時 | 2024-11-28 22:51:00 |
合計ジャッジ時間 | 11,659 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;#define rep(i, n) for(int i=0;i<(n);++i)#define rep1(i, n) for(int i=1;i<=(n);i++)#define ll long longusing mint = modint998244353;using P = pair<ll,ll>;using lb = long double;using T = tuple<ll, ll, ll>;#ifdef LOCAL# include <debug_print.hpp># define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)#else# define dbg(...) (static_cast<void>(0))#endifint main(){int n, m;cin >> n >> m;vector<int> a(n);rep(i,n) a[i] = i;rep(i,m){int t;cin >> t;vector<int> b(t);rep(j,t){cin >> b[j];--b[j];}reverse(b.begin(),b.end());rep(j,t-1){swap(a[b[j]], a[b[j+1]]);}}scc_graph g(n);rep(i,n){g.add_edge(i, a[i]);}dbg(a);auto res = g.scc();map<int, int> mp;for(auto vs : res){int v = vs.size();for(int r=2;r*r<=v;r++){if(v%r==0){int cnt = 0;while(v%r==0) {v /=r;cnt++;}mp[r] = max(mp[r], cnt);}}if(v!=1){mp[v] = max(mp[v], 1);}}mint ans = 1;for(auto p : mp){ans *= mint(p.first).pow(p.second);}cout << ans.val() << endl;return 0;}