問題一覧 > 教育的問題

No.3578 Adjacent Inversion Number

レベル : / AI推定難易度 : 500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 24
作問者 : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10247 / 自分の提出
問題文最終更新日: 2026-07-03 11:14:05
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 503 (順位表) の他の問題:

Problem Statement

You are given $2$ positive integers $N, B$ as input.

 

Here, a permutation of length $N$ consisting of positive integers at most $N$ is simply called a permutation of size $N$.

For a permutation $p$ of size $N$, let $f(p)$ denote the number of positive integers $i$ less than $N$ satisfying $p_i > p_{i+1}$.

Here, for a permutation $p$ of size $N$ and each positive integer $i$ at most $N$, $p_i$ denotes the $i$-th element of $p$.

 

When a permutation $p$ of size $N$ is chosen at random (so that each one is chosen with equal probability), determine whether the value of the expected value of $f(p)$ modulo $B$ exists, and if it exists, find that value.

 

Here, the value of a rational number $x$ modulo $B$ means the unique integer $r$ satisfying the following conditions.

  • $0 \leq r < B$.
  • When the irreducible fraction representation of $x$ is written as $\frac{n}{d}$ ($d$ is a positive integer and $n$ is an integer coprime to $d$), $n \equiv dr \pmod{B}$.

Note that such an $r$ exists if and only if $d$ and $B$ are coprime (there is no prime dividing both of them).

Input

The input is given from standard input in $1$ line in the following format:

  • The $1$st line contains $N, B$ separated by a single space.
$N$ $B$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 10^5$.
  • $B$ is an integer satisfying $1 \leq B \leq 10^9$.

Output

If the value of the expected value of $f(p)$ modulo $B$ exists, output it on $1$ line.

If it does not exist, output NaN.

Finally, output a newline.

Sample

Sample 1
Input
1 1
Output
0

The only permutation $p$ of size $N = 1$ is $(1)$. Since $f((1)) = 0$, the expected value of $f(p)$ is $\frac{0}{1} = 0$. Output $0$, the value of $0$ modulo $B = 1$.

Sample 2
Input
2 2
Output
NaN

The permutations $p$ of size $N = 2$ are $(1,2)$ and $(2,1)$. Since $f((1,2)) = 0$ and $f((2,1)) = 1$, the expected value of $f(p)$ is $\frac{0+1}{2} = \frac{1}{2}$. The value of $\frac{1}{2}$ modulo $B = 2$ does not exist, so output NaN.

Sample 3
Input
3 5
Output
1

The permutations $p$ of size $N = 3$ are $(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$, $(3,1,2)$ and $(3,2,1)$. Since $f((1,2,3)) = 0$, $f((1,3,2)) = 1$, $f((2,1,3)) = 1$, $f((2,3,1)) = 1$, $f((3,1,2)) = 1$ and $f((3,2,1)) = 2$, the expected value of $f(p)$ is $\frac{0+1+1+1+1+2}{6} = 1$. Output $1$, the value of $1$ modulo $B = 5$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。