問題一覧 > 教育的問題

No.2396 Arithmetic Binomial Expansion

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 22
作問者 : 👑 p-adic / テスター : ecottea
お気に入りにしたユーザー ProblemId : 8842 / 自分の提出
問題文最終更新日: 2023-02-27 21:43:17
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 399 (順位表) の他の問題:

Note

The execution time limit for this problem is 6000[ms].

Problem Statement

You are given $3$ positive integers $N, M, L$, a non-negative integer $K$ less than $L$, and a positive integer $B$ as input.

 

Find the sum of $\binom{N}{L n + K} M^n$ over all non-negative integers $n$ satisfying $L n + K \leq N$, modulo $B$.

Input

The input is given from standard input in the following format:

$N$ $M$ $L$ $K$ $B$

$N, M, L, K, B$ are given on $1$ line, separated by single-byte spaces.

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 10^{18}$
  • $M$ is an integer satisfying $1 \leq M \leq 10^{18}$
  • $L$ is an integer satisfying $1 \leq L \leq 10^3$
  • $K$ is an integer satisfying $0 \leq K < L$
  • $B$ is an integer satisfying $1 \leq B \leq 10^9$

Output

Output on $1$ line the sum of $\binom{N}{L n + K} M^n$ over all non-negative integers $n$ satisfying $L n + K \leq N$, modulo $B$.

Print a newline at the end.

Sample

Sample 1
Input
1 3 2 1 2
Output
1

The only non-negative integer $n$ satisfying $2n + 1 \leq 1$ is $0$.

$\displaystyle \binom{N}{L \times 0 + K} M^0 = \binom{1}{1} 3^0 = 1 $

and the remainder of $1$ divided by $B = 2$ is $1$.

Sample 2
Input
1 1000000000000000000 4 2 3

Note that, as in this case, the input may not fit in a 32-bit integer.

Output
0

There is no non-negative integer $n$ satisfying $4n + 2 \leq 1$. Therefore, the sum to be found is $0$.

The remainder of $0$ divided by $B = 3$ is $0$.

Sample 3
Input
3 5 2 1 3
Output
2

The only non-negative integers $n$ satisfying $2n + 1 \leq 3$ are $0,1$.

$\displaystyle \binom{N}{L \times 0 + K} M^0 + \binom{N}{L \times 1 + K} M^1 = \binom{3}{1} 5^0 + \binom{3}{3} 5^1 = 3 + 5 = 8 $

and the remainder of $8$ divided by $B = 3$ is $2$.

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