結果
問題 | No.1428 PeRmutation Question |
ユーザー | 👑 箱 |
提出日時 | 2020-12-27 20:54:28 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 2,159 bytes |
コンパイル時間 | 7,380 ms |
コンパイル使用メモリ | 246,924 KB |
実行使用メモリ | 9,940 KB |
最終ジャッジ日時 | 2024-04-09 19:56:39 |
合計ジャッジ時間 | 9,078 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,812 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,944 KB |
testcase_12 | AC | 7 ms
6,940 KB |
testcase_13 | AC | 25 ms
6,944 KB |
testcase_14 | AC | 21 ms
6,944 KB |
testcase_15 | AC | 16 ms
6,944 KB |
testcase_16 | AC | 29 ms
9,140 KB |
testcase_17 | AC | 29 ms
9,380 KB |
testcase_18 | AC | 12 ms
6,944 KB |
testcase_19 | AC | 9 ms
6,940 KB |
testcase_20 | AC | 10 ms
6,940 KB |
testcase_21 | AC | 26 ms
6,944 KB |
testcase_22 | AC | 31 ms
9,172 KB |
testcase_23 | AC | 32 ms
8,924 KB |
testcase_24 | AC | 30 ms
8,660 KB |
testcase_25 | AC | 26 ms
6,944 KB |
testcase_26 | AC | 26 ms
6,940 KB |
testcase_27 | AC | 31 ms
8,676 KB |
testcase_28 | AC | 27 ms
6,940 KB |
testcase_29 | AC | 31 ms
9,940 KB |
testcase_30 | AC | 31 ms
8,804 KB |
testcase_31 | AC | 29 ms
8,676 KB |
testcase_32 | AC | 29 ms
8,680 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <cassert> #include "testlib.h" using ll = long long; using namespace std; #define rep(i,n) for (int i = 0; i < (n); i++) const ll MOD = 1000000007; ll modpow(ll a, ll n, ll mod) { ll res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } ll modinv(ll i, ll mod) { return modpow(i, mod - 2, mod); } ll fact(ll n, ll mod) { ll ans = 1; rep(i, n) { ans = ans * (i + 1) % mod; } return ans; } ll comb(ll n, ll a, ll mod) { ll ans = 1, denom = 1; rep(i, a) { ans = ans * (n - i) % mod; denom = denom * (i + 1) % mod; } ans = ans * modinv(denom, mod) % mod; return ans; } int main(int argc, char* argv[]) { registerValidation(argc, argv); int n = inf.readInt(1, 100000, "n"); inf.readEoln(); vector<int> p(n); vector<int> counter(n, 0); for (size_t i = 0; i < n; i++) { p[i] = inf.readInt(1, n, "p_i"); if (i != n - 1) { inf.readSpace(); } p[i]--; counter[p[i]]++; } inf.readEoln(); inf.readEof(); for (size_t i = 0; i < n; i++) { assert(counter[i] == 1); } map<int, int> mp; vector<bool> visited(n, false); for (size_t i = 0; i < n; i++) { if (!visited[i]) { int l = 0; int v = i; while (!visited[v]) { visited[v] = true; v = p[v]; l++; } mp[l]++; } } bool half = true; ll ans = fact(n, MOD); for (auto itr = mp.begin(); itr != mp.end(); ++itr) { int k = itr->first; int v = itr->second; if (k % 2 == 0 || v >= 2) { half = false; } ans *= modinv(modpow(k, v, MOD), MOD); ans %= MOD; ans *= modinv(fact(v, MOD), MOD); ans %= MOD; } if (half && n != 1) { ans *= modinv(2, MOD); ans %= MOD; } cout << ans << "\n"; }