結果

問題 No.2428 Returning Shuffle
ユーザー siman
提出日時 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.

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0