No.3495 Two-Variable Half Binomial Expansion
タグ : / 解いたユーザー数 11
作問者 : 👑
Problem Statement
Consider the following problem:
You are given $4$ positive integers $N, M, L, B$ as input.
$\displaystyle \sum_{n=0}^{\lfloor \frac{N}{2} \rfloor} \binom{N}{2n} M^n L^{\lfloor \frac{N}{2} \rfloor - n} $
Find the remainder when the above value is divided by $B$. This value is called the answer to this problem.
Here, $\lfloor \frac{N}{2} \rfloor$ denotes the greatest integer not exceeding $\frac{N}{2}$.
A positive integer $T$ is given at the beginning of the input. Answer $T$ problems.
Input
For each positive integer $t$ not exceeding $T$, the input $N,M,L,B$ for the $t$-th problem is denoted by $N_t,M_t,L_t,B_t$.
The input is given from standard input in $1 + T$ lines in the following format:
- Line $1$ contains $T$.
- For each positive integer $t$ not exceeding $T$, line $1 + t$ contains $N_t,M_t,L_t,B_t$, separated by single-byte spaces.
$T$ $N_1$ $M_1$ $L_1$ $B_1$ $\vdots$ $N_T$ $M_T$ $L_T$ $B_T$
Constraints
The input satisfies the following constraints:
- $T$ is an integer satisfying $1 \leq T \leq 10^4$.
- For every positive integer $t$ not exceeding $T$:
- $N_t$ is an integer satisfying $1 \leq N_t \leq 10^{18}$.
- $M_t$ is an integer satisfying $1 \leq M_t \leq 10^{18}$.
- $L_t$ is an integer satisfying $1 \leq L_t \leq 10^{18}$.
- $B_t$ is an integer satisfying $1 \leq B_t \leq 10^9$.
Output
For each positive integer $t$ not exceeding $T$, print the answer to the $t$-th problem on line $t$.
Print a newline at the end.
Sample
Sample 1
Input
4 1 1 2 3 2 2 3 5 3 1 2 3 4 2 1 3
Output
1 0 2 2
For the $1$st problem,
$\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 $
and the remainder when $1$ is divided by $B = 3$ is $1$.
For the $2$nd problem,
$\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 $
and the remainder when $5$ is divided by $B = 5$ is $0$.
For the $3$rd problem,
$\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 $
and the remainder when $5$ is divided by $B = 3$ is $2$.
For the $4$th problem,
$\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 $
and the remainder when $17$ is divided by $B = 3$ is $2$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。