問題一覧 > 通常問題

No.2181 LRM Question 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : MasKoaTSMasKoaTS / テスター : 37zigen37zigen 👑 potato167potato167
0 ProblemId : 8422 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-01-06 17:34:53

問題文

正整数 $L, R, M$ が与えられます。次の値を $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)$

なお、本問の制約下において、上式の値は必ず非負整数となることが保証されます。

> $\sum, \prod$ の定義(クリックで展開)

任意の長さ $n$ の数列 $a = ( a_{1}, a_{2}, \dots, a_{n} )$ に対して、$\displaystyle \sum_{i=l}^{r} a_{i}$ 及び $\displaystyle \prod_{i=l}^{r} a_{i}$ は次のように定義されます。

  • $\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}$

ただし、$n,l,r$ はいずれも $1 \leq l \leq r \leq n$ を満たす整数とします。

制約

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

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

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

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

$L$ $R$ $M$
  • $1$ 行目には $L, R, M$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力してください。

サンプル

サンプル1
入力
2 5 8
出力
4

$\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)$ として、 $$ \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} $$ とすると、 $$ g_{2}(n) = \sum_{i=1}^{n-1} ( h_{1}(i) \times h_{2}(i) ) $$ であり、 $$ f(L,R) = \sum_{n=L}^{R} ( g_{1}(n) \times g_{2}(n) ) $$ です。

このとき、$f(2,5) = 340$ であり、これを $8$ で割った余りは $4$ となります。

サンプル2
入力
2 2 2
出力
0

$f(2,2) = 4$ であり、これは $2$ で割り切れます。

サンプル3
入力
999999999999900000 1000000000000000000 1000000
出力
599998

$f(L,R)$ の値は非常に大きくなる可能性があります。

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