結果
問題 | No.2428 Returning Shuffle |
ユーザー |
![]() |
提出日時 | 2023-08-30 17:40:28 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 235 ms / 2,000 ms |
コード長 | 2,341 bytes |
コンパイル時間 | 4,862 ms |
コンパイル使用メモリ | 151,524 KB |
実行使用メモリ | 14,828 KB |
最終ジャッジ日時 | 2025-01-02 11:15:59 |
合計ジャッジ時間 | 8,249 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
コンパイルメッセージ
main.cpp:23:18: warning: variable length arrays in C++ are a Clang extension [-Wvla-cxx-extension] 23 | bool checked[MAX_N + 1]; | ^~~~~~~~~ main.cpp:23:18: note: implicit use of 'this' pointer is only allowed within the evaluation of a call to a 'constexpr' member function main.cpp:70:9: warning: variable length arrays in C++ are a Clang extension [-Wvla-cxx-extension] 70 | int P[N]; | ^ main.cpp:70:9: note: read of non-const variable 'N' is not allowed in a constant expression main.cpp:68:7: note: declared here 68 | int N, M; | ^ main.cpp:78:11: warning: variable length arrays in C++ are a Clang extension [-Wvla-cxx-extension] 78 | int S[t]; | ^ main.cpp:78:11: note: read of non-const variable 't' is not allowed in a constant expression main.cpp:76:9: note: declared here 76 | int t; | ^ main.cpp:95:16: warning: variable length arrays in C++ are a Clang extension [-Wvla-cxx-extension] 95 | bool visited[N]; | ^ main.cpp:95:16: note: read of non-const variable 'N' is not allowed in a constant expression main.cpp:68:7: note: declared here 68 | int N, M; | ^ 4 warnings generated.
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <numeric> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; class Prime { public: vector<ll> prime_list; const ll MAX_N = 1000000; Prime() { bool checked[MAX_N + 1]; memset(checked, false, sizeof(checked)); for (ll i = 2; i <= MAX_N; ++i) { if (!checked[i]) { prime_list.push_back(i); for (ll j = i * i; j <= MAX_N; j += i) { checked[j] = true; } } } } map<ll, int> prime_division(ll n) { map<ll, int> res; for (ll i = 0; prime_list[i] <= sqrt(n); ++i) { ll p = prime_list[i]; while (n % p == 0) { ++res[p]; n /= p; } } if (n != 1) { res[n] = 1; } return res; } bool is_prime(ll n) { if (n <= 1) return false; for (int i = 0; i < prime_list.size(); ++i) { if (n % prime_list[i]) return false; } return true; } }; int main() { int N, M; cin >> N >> M; int P[N]; for (int n = 0; n < N; ++n) { P[n] = n; } for (int i = 0; i < M; ++i) { int t; scanf("%d", &t); int S[t]; for (int j = 0; j < t; ++j) { scanf("%d", &S[j]); } int temp = P[S[0] - 1]; for (int j = 0; j < t; ++j) { int next = S[(j + 1) % t] - 1; int old = P[next]; P[next] = temp; temp = old; } } bool visited[N]; memset(visited, false, sizeof(visited)); vector<ll> nums; for (int v = 0; v < N; ++v) { if (visited[v]) continue; queue<int> que; que.push(v); int size = 0; while (not que.empty()) { int x = que.front(); que.pop(); if (visited[x]) continue; visited[x] = true; ++size; que.push(P[x]); } nums.push_back(size); } ll MOD = 998244353; ll ans = 1; Prime prime; map<ll, int> values; for (ll x : nums) { map<ll, int> res = prime.prime_division(x); for (auto [n, e] : res) { values[n] = max(values[n], e); } } for (auto [n, e] : values) { ll v = 1; for (int i = 0; i < e; ++i) { v *= n; v %= MOD; } ans *= v; ans %= MOD; } cout << ans << endl; return 0; }