結果
問題 | No.1428 PeRmutation Question |
ユーザー |
![]() |
提出日時 | 2021-03-12 22:37:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 1,827 bytes |
コンパイル時間 | 3,563 ms |
コンパイル使用メモリ | 187,208 KB |
最終ジャッジ日時 | 2025-01-19 15:18:19 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; using mint=modint1000000007; mint f[2000010], invf[2000010]; void fac(int n){ f[0]=1; for(ll i=1; i<=n; i++) f[i]=f[i-1]*i; invf[n]=f[n].inv(); for(ll i=n-1; i>=0; i--) invf[i]=invf[i+1]*(i+1); } mint comb(int x, int y){ if(!(0<=y && y<=x)) return 0; return f[x]*invf[y]*invf[x-y]; } int main() { int n; cin>>n; int p[100010]; for(int i=0; i<n; i++){ cin>>p[i]; p[i]--; } vector<int> v; bool used[100010]={}; for(int i=0; i<n; i++){ if(used[i]) continue; int c=0, x=i; do{ used[x]=1; x=p[x]; c++; }while(!used[x]); v.push_back(c); } bool allodd=1; for(auto c:v) if(c%2==0) allodd=0; fac(n); map<int, int> mp; for(auto c:v) mp[c]++; if(!allodd){ mint ans=f[n]; for(auto c:v) ans/=c; for(auto p:mp) ans*=invf[p.second]; cout<<ans.val()<<endl; }else{ mint ans=f[n]; bool all1=1; for(auto c:v){ if(c>1) all1=0; } if(all1) cout<<1<<endl; else{ for(auto c:v) ans/=c; ans/=2; cout<<ans.val()<<endl; } } return 0; }