No.2581 [Cherry Anniversary 3] Bouquet of 28 Cherry Blossoms
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.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun