No.2396 等差二項展開
タグ : / 解いたユーザー数 24
作問者 : 👑
p-adic
/ テスター :
ecottea
注意
この問題の実行時間制限は6000[ms]です。
問題文
入力に $3$ 個の正整数 $N, M, L$ と、$L$ 未満の非負整数 $K$ と、正整数 $B$ が与えられます。
$L n + K \leq N$ を満たす全ての非負整数 $n$ をわたる $\binom{N}{L n + K} M^n$ の総和を $B$ で割った余りを求めてください。
入力
入力は次の形式で標準入力から与えられます：
$N$ $M$ $L$ $K$ $B$
$1$ 行に $N, M, L, K, B$ が半角空白区切りで与えられます。
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^{18}$ を満たす整数
- $M$ は $1 \leq M \leq 10^{18}$ を満たす整数
- $L$ は $1 \leq L \leq 10^3$ を満たす整数
- $K$ は $0 \leq K < L$ を満たす整数
- $B$ は $1 \leq B \leq 10^9$ を満たす整数
出力
$L n + K \leq N$ を満たす全ての非負整数 $n$ をわたる $\binom{N}{L n + K} M^n$ の総和を $B$ で割った余りを $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 3 2 1 2
出力
1
$2n + 1 \leq 1$ を満たす非負整数 $n$ は $0$ に限られます。
$\displaystyle \binom{N}{L \times 0 + K} M^0 = \binom{1}{1} 3^0 = 1 $
であり、$1$ を $B = 2$ で割った余りは $1$ です。
サンプル2
入力
1 1000000000000000000 4 2 3
このように入力が32bit整数に収まらない場合があることに注意してください。
出力
0
$4n + 2 \leq 1$ を満たす非負整数 $n$ は存在しません。従って求める総和は $0$ となります。
$0$ を $B = 3$ で割った余りは $0$ です。
サンプル3
入力
3 5 2 1 3
出力
2
$2n + 1 \leq 3$ を満たす非負整数 $n$ は $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 $
であり、$8$ を $B = 3$ で割った余りは $2$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。