問題一覧 > 通常問題

No.2181 LRM Question 2

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 24
作問者 : MasKoaTS / テスター : 37zigen 👑 potato167
お気に入りにしたユーザー ProblemId : 8422 / 自分の提出
問題文最終更新日: 2024-11-28 20:40:38
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 372 (順位表) の他の問題:

Problem Statement

You are given positive integers $L, R, M$. Find the remainder when the following value is divided by $M$.

$\displaystyle \sum_{n=L}^{R} \left( \left( \prod_{i=1}^{n} \dfrac{ 1 }{ i^{2} } \right) \sum_{i=1}^{n-1} \left( \prod_{j=1}^{i} (n - j + 1)^{2} \prod_{j=i+1}^{n} j^{2} \right) \right)$

It is guaranteed that, under the constraints of this problem, the value of the above expression is always a non-negative integer.

Definition of $\sum, \prod$ (click to expand)

For a sequence $a = ( a_{1}, a_{2}, \dots, a_{n} )$ of length $n$, $\displaystyle \sum_{i=l}^{r} a_{i}$ and $\displaystyle \prod_{i=l}^{r} a_{i}$ are defined as follows.

  • $\displaystyle \sum_{i=l}^{r} a_{i} = a_{l} + a_{l+1} + \cdots + a_{r}$

  • $\displaystyle \prod_{i=l}^{r} a_{i} = a_{l} \times a_{l+1} \times \cdots \times a_{r}$

Here, $n,l,r$ are all integers satisfying $1 \leq l \leq r \leq n$.

Constraints

  • $2 \leq L \leq R \leq 10^{18}$

  • $R - L \leq 10^{5}$

  • $1 \leq M \leq 10^{6}$

  • All input values are integers.

Input

The input is given in the following format.

$L$ $R$ $M$

  • The $1$st line contains $L, R, M$ in this order, separated by single spaces.

Output

Output the answer in $1$ line.

Sample

Sample 1
Input
2 5 8
Output
4

Let $\displaystyle f(L,R) = \sum_{n=L}^{R} \left( \left( \prod_{i=1}^{n} \dfrac{ 1 }{ i^{2} } \right) \sum_{i=1}^{n-1} \left( \prod_{j=1}^{i} (n - j + 1)^{2} \prod_{j=i+1}^{n} j^{2} \right) \right)$, and let $$ \begin{aligned} &g_{1}(n) = \prod_{i=1}^{n} \dfrac{ 1 }{ i^{2} }, \\ &g_{2}(n) = \sum_{i=1}^{n-1} \left( \prod_{j=1}^{i} (n - j + 1)^{2} \prod_{j=i+1}^{n} j^{2} \right), \\ &h_{1}(i) = \prod_{j=1}^{i} (n - j + 1)^{2}, \\ &h_{2}(i) = \prod_{j=i+1}^{n} j^{2} \end{aligned} $$ Then, $$ g_{2}(n) = \sum_{i=1}^{n-1} ( h_{1}(i) \times h_{2}(i) ) $$ and $$ f(L,R) = \sum_{n=L}^{R} ( g_{1}(n) \times g_{2}(n) ) $$ hold.

In this case, $f(2,5) = 340$, and the remainder when this is divided by $8$ is $4$.

Sample 2
Input
2 2 2
Output
0

$f(2,2) = 4$, which is divisible by $2$.

Sample 3
Input
999999999999900000 1000000000000000000 1000000
Output
599998

The value of $f(L,R)$ can be very large.

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