問題一覧 > 通常問題

No.2181 LRM Question 2

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

問題文

正整数 L,R,ML, R, M が与えられます。次の値を MM で割った余りを求めてください。

n=LR((i=1n1i2)i=1n1(j=1i(nj+1)2j=i+1nj2))\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 の定義(クリックで展開)

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

  • i=lrai=al+al+1++ar\displaystyle \sum_{i=l}^{r} a_{i} = a_{l} + a_{l+1} + \cdots + a_{r}

  • i=lrai=al×al+1××ar\displaystyle \prod_{i=l}^{r} a_{i} = a_{l} \times a_{l+1} \times \cdots \times a_{r}

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

制約

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

  • RL105R - L \leq 10^{5}

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

  • 入力はすべて整数

入力

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

LL RR MM
  • 11 行目には L,R,ML, R, M がこの順に半角スペース区切りで与えられる

出力

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

サンプル

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

f(L,R)=n=LR((i=1n1i2)i=1n1(j=1i(nj+1)2j=i+1nj2))\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) として、 g1(n)=i=1n1i2,g2(n)=i=1n1(j=1i(nj+1)2j=i+1nj2),h1(i)=j=1i(nj+1)2,h2(i)=j=i+1nj2 \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} とすると、 g2(n)=i=1n1(h1(i)×h2(i)) g_{2}(n) = \sum_{i=1}^{n-1} ( h_{1}(i) \times h_{2}(i) ) であり、 f(L,R)=n=LR(g1(n)×g2(n)) f(L,R) = \sum_{n=L}^{R} ( g_{1}(n) \times g_{2}(n) ) です。

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

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

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

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

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

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