問題一覧 > 教育的問題

No.3495 Two-Variable Half Binomial Expansion

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : 👑 p-adic
お気に入りにしたユーザー ProblemId : 9265 / 自分の提出
問題文最終更新日: 2026-04-03 19:33:57
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 496 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。