No.3495 ２変数半二項展開
p-adic問題文
以下の問題を考えます：
入力に $4$ 個の正整数 $N, M, L, B$ が与えられます。
$\displaystyle \sum_{n=0}^{\lfloor \frac{N}{2} \rfloor} \binom{N}{2n} M^n L^{\lfloor \frac{N}{2} \rfloor - n} $
を $B$ で割った余りを求めてください。この値をこの問題に対する答えと呼びます。
ただし $\lfloor \frac{N}{2} \rfloor$ は $\frac{N}{2}$ を超えない最大の整数を表します。
入力の最初に 正整数 $T$ が与えられます。$T$ 個の問題に答えてください。
入力
$T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する入力 $N,M,L,B$ を $N_t,M_t,L_t,B_t$ と書き表します。
入力は以下の形式で標準入力から $1 + T$ 行で与えられます：
- $1$ 行目に $T$ が与えられます。
- $T$ 以下の各正整数 $t$ に対し、$1 + t$ 行目に $N_t,M_t,L_t,B_t$ が半角空白区切りで与えられます。
$T$ $N_1$ $M_1$ $L_1$ $B_1$ $\vdots$ $N_T$ $M_T$ $L_T$ $B_T$
制約
入力は以下の制約を満たします：
- $T$ は $1 \leq T \leq 10^4$ を満たす整数である。
- $T$ 以下の任意の正整数 $t$ に対し、
- $N_t$ は $1 \leq N_t \leq 10^{18}$ を満たす整数である。
- $M_t$ は $1 \leq M_t \leq 10^{18}$ を満たす整数である。
- $L_t$ は $1 \leq L_t \leq 10^{18}$ を満たす整数である。
- $B_t$ は $1 \leq B_t \leq 10^9$ を満たす整数である。
出力
$T$ 以下の各正整数 $t$ に対し、$t$ 行目に $t$ 個目の問題に対する答えを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
4 1 1 2 3 2 2 3 5 3 1 2 3 4 2 1 3
出力
1 0 2 2
$1$ 個目の問題について、
$\displaystyle \sum_{n=0}^{\lfloor \frac{N}{2} \rfloor} \binom{N}{2n} M^n L^{\lfloor \frac{N}{2} \rfloor - n} = \binom{1}{0} 1^0 2^0 = 1 $
であり、$1$ を $B = 3$ で割った余りは $1$ です。
$2$ 個目の問題について、
$\displaystyle \sum_{n=0}^{\lfloor \frac{N}{2} \rfloor} \binom{N}{2n} M^n L^{\lfloor \frac{N}{2} \rfloor - n} = \binom{2}{0} 2^0 3^1 + \binom{2}{2} 2^1 3^0 = 3 + 2 = 5 $
であり、$5$ を $B = 5$ で割った余りは $0$ です。
$3$ 個目の問題について、
$\displaystyle \sum_{n=0}^{\lfloor \frac{N}{2} \rfloor} \binom{N}{2n} M^n L^{\lfloor \frac{N}{2} \rfloor - n} = \binom{3}{0} 1^0 2^1 + \binom{3}{2} 1^1 2^0 = 2 + 3 = 5 $
であり、$5$ を $B = 3$ で割った余りは $2$ です。
$4$ 個目の問題について、
$\displaystyle \sum_{n=0}^{\lfloor \frac{N}{2} \rfloor} \binom{N}{2n} M^n L^{\lfloor \frac{N}{2} \rfloor - n} = \binom{4}{0} 2^0 1^2 + \binom{4}{2} 2^1 1^1 + \binom{4}{4} 2^2 1^0 = 1 + 12 + 4 = 17 $
であり、$17$ を $B = 3$ で割った余りは $2$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。