結果
問題 | No.2428 Returning Shuffle |
ユーザー |
![]() |
提出日時 | 2023-08-18 21:54:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,259 ms / 2,000 ms |
コード長 | 3,389 bytes |
コンパイル時間 | 2,804 ms |
コンパイル使用メモリ | 182,424 KB |
実行使用メモリ | 141,180 KB |
最終ジャッジ日時 | 2024-11-28 06:52:52 |
合計ジャッジ時間 | 29,998 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll =long long;#define all(v) v.begin(),v.end()#define rep(i,a,b) for(int i=a;i<b;i++)#define rrep(i,a,b) for(int i=a;i>=b;i--)ll INF=2e18;struct UnionFind {vector<pair<ll,ll>> par;vector<ll> r;void init(ll n) {par=vector<pair<ll,ll>> (n);r=vector<ll> (n);for(ll i=0;i<n;i++) {par[i]=make_pair(i,1);r[i]=0LL;}}ll find(ll x) {if(par[x].first==x) {return x;}return par[x].first=find(par[x].first);}void unite(ll x,ll y) {x=find(x);y=find(y);if(x==y) {return;}if(r[x]<r[y]) {par[x].first=y;par[y].second+=par[x].second;}else {par[y].first=x;par[x].second+=par[y].second;if(r[x]==r[y]) {r[x]++;}}}bool same(ll x,ll y) {return find(x)==find(y);}};const int mod = 998244353;class mint {long long x;public:mint(long long x=0) : x((x%mod+mod)%mod) {}mint operator-() const {return mint(-x);}mint& operator+=(const mint& a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint& a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint& a) {(x *= a.x) %= mod;return *this;}mint operator+(const mint& a) const {mint res(*this);return res+=a;}mint operator-(const mint& a) const {mint res(*this);return res-=a;}mint operator*(const mint& a) const {mint res(*this);return res*=a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}// for prime modmint inv() const {return pow(mod-2);}mint& operator/=(const mint& a) {return (*this) *= a.inv();}mint operator/(const mint& a) const {mint res(*this);return res/=a;}friend ostream& operator<<(ostream& os, const mint& m){os << m.x;return os;}};int main() {ios::sync_with_stdio(false);cin.tie(0);ll N,M;cin>>N>>M;vector<ll> P(N+1);for(ll i=1;i<=N;i++) P[i]=i;for(ll i=0;i<M;i++) {ll T;cin>>T;vector<ll> S(T);for(ll j=0;j<T;j++) cin>>S[j];ll memo=P[S[T-1]];for(ll j=T-1;j>=1;j--) {P[S[j]]=P[S[j-1]];}P[S[0]]=memo;}UnionFind uf;uf.init(N+1);for(ll i=1;i<=N;i++) {uf.unite(P[i],i);}vector<bool> note(N+1);vector<ll> vec(0);for(ll i=1;i<=N;i++) {ll k=uf.find(i);if(!note[k]) {note[k]=true;vec.push_back(uf.par[k].second);}}vector<ll> prime(0);vector<bool> memo(1000000+100);for(ll i=2;i<=1000000;i++) {if(!memo[i]) {prime.push_back(i);for(ll j=1;j*i<=1000000;j++) memo[j*i]=true;}}vector<vector<pair<ll,ll>>> d(1000000+100,vector<pair<ll,ll>> (0));for(auto x:prime) {for(ll j=1;j*x<=1000000;j++) {ll count=0;ll now=j*x;while(now%x==0) {now/=x;count++;}d[j*x].push_back(make_pair(x,count));}}mint ans=1;vector<ll> ma(1000000+10);for(ll i=0;i<vec.size();i++) {for(auto x:d[vec[i]]) {while(ma[x.first]<x.second) {ma[x.first]++;ans*=x.first;}}}cout<<ans<<endl;}