No.1428 PeRmutation Question
レベル :
/ AI推定難易度 : 2250
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : 👑
箱星
/ テスター :
butsurizuki
タグ : / 解いたユーザー数 20
作問者 : 👑
butsurizuki
問題文最終更新日: 2022-04-26 00:01:45
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 286
(順位表)
の他の問題:
Problem Statement
You are given a permutation $P$ of $1,2,\ldots, N$.
Find the number of permutations $Q$ of $1,2,\ldots,N$ that satisfy the following condition.
- (Condition on $Q$) There exists a permutation $R$ of $1,2,\ldots,N$ that satisfies the following $2$ conditions.
- (Condition $1$ on $R$) $P_{R_i}=R_{Q_i} \ (i=1,2,\ldots,N)$
- (Condition $2$ on $R$) The inversion number of $R$ is even.
Since the answer can be very large, find the answer modulo $10^9+7$.
Input
$N$ $P_1$ $P_2$ $\ldots$ $P_N$
- All inputs are integers.
- $1\le N\le 10^5$
- $P_1,P_2,\ldots,P_N$ is a permutation of $1,2,\ldots,N$.
Output
Find the number of permutations satisfying the condition, and output it modulo $10^9+7$.
Sample
Sample 1
Input
4 2 1 4 3
Output
3
For example, $Q=(4,3,2,1)$ satisfies the condition by taking $R=(3,1,2,4)$.
Sample 2
Input
1 1
Output
1
Sample 3
Input
9 3 5 1 8 9 7 4 6 2
Output
15120
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。