結果
問題 | No.1978 Permutation Repetition |
ユーザー |
![]() |
提出日時 | 2022-06-10 12:37:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 2,335 bytes |
コンパイル時間 | 7,089 ms |
コンパイル使用メモリ | 301,064 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-21 05:44:53 |
合計ジャッジ時間 | 8,232 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 44 |
ソースコード
#include <bits/stdc++.h>#include "testlib.h"using namespace std;#define MOD 1000000007long long gcd(long long x, long long y) {if (x < y) swap(x, y);while (y > 0) {long long r = x % y;x = y;y = r;}return x;}long long lcm(long long x, long long y) {return x * y / gcd(x, y);}const int MAX = 1020;long long fac[MAX], finv[MAX], inv[MAX];void COMinit(long long mod) {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++) {fac[i] = fac[i - 1] * i % mod;inv[i] = mod - inv[mod % i] * (mod / i) % mod;finv[i] = finv[i - 1] * inv[i] % mod;}}long long COM(long long n, long long k, long long mod) {if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % mod) % mod;}long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}int main() {COMinit(MOD);long long N, M;registerValidation();N = inf.readInt(1, 1000, "N");inf.readSpace();M = inf.readInt(1, 1000000000, "M");vector<long long> A(N);inf.readEoln();A[0] = inf.readInt(1, N, "A");for (int i = 1; i < N; i++) {inf.readSpace();A[i] = inf.readInt(1, N, "A");}inf.readEoln();inf.readEof();vector<bool> flagtest(N, false);for (int i = 0; i < N; i++){if (flagtest[A[i] - 1]) cout << -1 << endl;flagtest[A[i] - 1] = true;}vector<long long> chikan(N + 1);vector<bool> flag(N, false);for (int i = 0; i < N; i++) {if (flag[i]) continue;int i_ = A[i] - 1;flag[i_] = true;int count = 1;while (i != i_) {i_ = A[i_] - 1;count++;flag[i_] = true;}chikan[count]++;}vector<vector<long long>> jun(N + 1);for (int i = 1; i <= N; i++) {jun[i / gcd(i, M)].push_back(i);}long long ans = 1;for (int i = 1; i <= N; i++) {vector<long long> dp(chikan[i] + 1, 0);dp[0] = 1;for (int j = 1; j <= chikan[i]; j++) {for (int k = 0; k < jun[i].size(); k++) {if (j < jun[i][k] / i) continue;dp[j] += ((dp[j - jun[i][k] / i] * COM(j - 1, jun[i][k] / i - 1, MOD) % MOD) * fac[jun[i][k] / i - 1] % MOD) * modpow(i, jun[i][k] /i - 1, MOD) % MOD;}dp[j] %= MOD;}ans = ans * dp[chikan[i]] % MOD;}cout << ans << endl;}