問題一覧 > 通常問題

No.2581 [Cherry Anniversary 3] Bouquet of 28 Cherry Blossoms

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 40
作問者 : 👑 Kazun / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10129 / 自分の提出
問題文最終更新日: 2023-12-08 00:26:55
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
Advent Calendar Contest 2023 (順位表) の他の問題:

Problem Statement

Cherry-chan is going to make a bouquet using $28$ cherry blossoms.

The bouquet she is making is divided into $28$ parts, and each part uses $1$ blossom of exactly one of the two varieties: Somei Yoshino or Satozakura.

For each part, its brilliance is determined by the variety of blossom used. Specifically, for $i=1,2, \dots, 28$, it is as follows.

  • If Somei Yoshino is used for the $i$-th part, the brilliance of the $i$-th part is $G_i$.
  • If Satozakura is used for the $i$-th part, the brilliance of the $i$-th part is $H_i$.

For a completed bouquet consisting of $28$ parts, its beauty is defined as follows.

  • The remainder when the sum of the brilliance over all $28$ parts is divided by $M$.

For each of $q=1,2, \dots, Q$, answer the following question.

  • Find the number of ways to make a bouquet satisfying the following $2$ conditions.
    • Among the $28$ parts, exactly $K_q$ parts use Somei Yoshino.
    • The beauty of the bouquet is at least $X_q$.

Here, for $2$ bouquets, these $2$ bouquets are considered different if and only if there exists a part that uses Somei Yoshino in one and Satozakura in the other.

Constraints

  • $2 \leq M \leq 10^9$.
  • $0 \leq G_i \lt M \quad (1 \leq i \leq 28)$.
  • $0 \leq H_i \lt M \quad (1 \leq i \leq 28)$.
  • $1 \leq Q \leq 100$.
  • Constraints for each question.
    • $0 \leq K_q \leq 28 \quad (1 \leq q \leq Q)$.
    • $0 \leq X_q \lt M \quad (1 \leq q \leq Q)$.
  • All inputs are integers.

Input

$M$
$G_1$ $G_2$ $G_3$ $G_4$ $G_5$ $G_6$ $G_7$ $G_8$ $G_9$ $G_{10}$ $G_{11}$ $G_{12}$ $G_{13}$ $G_{14}$ $G_{15}$ $G_{16}$ $G_{17}$ $G_{18}$ $G_{19}$ $G_{20}$ $G_{21}$ $G_{22}$ $G_{23}$ $G_{24}$ $G_{25}$ $G_{26}$ $G_{27}$ $G_{28}$
$H_1$ $H_2$ $H_3$ $H_4$ $H_5$ $H_6$ $H_7$ $H_8$ $H_9$ $H_{10}$ $H_{11}$ $H_{12}$ $H_{13}$ $H_{14}$ $H_{15}$ $H_{16}$ $H_{17}$ $H_{18}$ $H_{19}$ $H_{20}$ $H_{21}$ $H_{22}$ $H_{23}$ $H_{24}$ $H_{25}$ $H_{26}$ $H_{27}$ $H_{28}$
$Q$
$K_1$ $X_1$
$K_2$ $X_2$
$\vdots$
$K_Q$ $X_Q$

Output

The output consists of $Q$ lines. On the $q~(1 \leq q \leq Q)$-th line, print the answer to the $q$-th question as an integer.

Sample

Sample 1
Input
46
5 5 5 5 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2
4 19
18 28
Output
1
6519260

For $q=1$, there is only $1$ way to make a bouquet satisfying the conditions, shown below.

  • Use Somei Yoshino for the $1,2,3,4$-th parts.
  • Use Satozakura for the remaining $24$ parts.
The beauty of the bouquet made this way is the remainder of $$G_1 + G_2 + G_3 + G_4 + H_5 + \dots + H_{28} = 20$$ divided by $46$, which is $20$.

Sample 2
Input
4646
104 1114 1023 215 129 417 418 1012 1219 323 1021 829 112 1013 710 102 928 113 109 725 707 412 217 1108 509 818 215 122
26 25 24 25 22 24 23 24 20 21 25 22 21 24 22 23 18 21 17 19 18 18 20 17 17 19 18 18
3
5 215
6 628
7 1018
Output
95888
325920
816163

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