結果

問題 No.1978 Permutation Repetition
ユーザー magsta
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#include "testlib.h"
using namespace std;
#define MOD 1000000007
long 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0