これは考察がしんどい。
https://yukicoder.me/problems/no/1428
問題
1~Nの順列Pが与えられる。
以下を満たす1~Nの順列Qは何通りか。
- Qに対し、以下を満たす1~Nの順列Rが存在する
- P[R[i]]=R[Q[i]]
- Rの転倒数は偶数
解法
詳細な考察はEditorialに任せるとして、結果としてはサイクルの形状(長さと同じ長さのサイクルの個数)がPとQで一致すれば、上記条件を満たす。
長さLのサイクルがK[L]個あるとして、が解。
int N; int P[101010]; int num[101010]; const ll mo=1000000007; int vis[101010]; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; ll fact=1; FOR(i,N) { cin>>P[i]; P[i]--; fact=fact*(i+1)%mo; } ll ret=1; FOR(i,N) if(vis[i]==0) { x=i; y=0; while(vis[x]==0) { y++; vis[x]=1; x=P[x]; } ret=ret*y%mo; num[y]++; ret=ret*num[y]%mo; } int ok=0; FOR(i,N) { if(num[i]>0&&i%2==0) ok=1; if(num[i]>1) ok=1; } if(num[N]) ok=1; if(ok==0) ret*=2; cout<<fact*modpow(ret)%mo<<endl; }
まとめ
これ本番に考察しきれる気がしないな。