問題一覧 > 通常問題

No.2709 1975 Powers

レベル : / AI推定難易度 : 550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 181
作問者 : Nafmo2 / テスター : dyktr_06 sepa38 ryota2357
お気に入りにしたユーザー ProblemId : 9986 / 自分の提出
問題文最終更新日: 2024-03-27 14:45:41
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 425 (MMA Contest 018) (順位表) の他の問題:

Problem Statement

There is a sequence $A = (A_1,A_2,\dots,A_N)$ consisting of $N$ integers.

Among the ways to choose $4$ distinct integers $a,b,c,d$ from $A$, find the number of ways that satisfy the following conditions.

  • $10^a+9^b+7^c+5^d$ leaves a remainder of $Q$ when divided by $P$
  • $a < b < c < d$

Input

$N \ P \ Q$
$A_1 \ A_2 \ \dots \ A_N$
  • $4 \leq N \leq 200$
  • $2 \leq Q < P \leq 10^5$
  • $1 \leq A_i \leq 2 \times 10^6$
  • $A_i \neq A_j \ (i \neq j)$
  • All inputs are integers

Output

Find and output the number of ways to choose 4 integers that satisfy the conditions.

Sample

Sample 1
Input
5 7 5
7 3 9 6 10
Output
1

Only the following tuple $a,b,c,d$ satisfies the condition of leaving a remainder of $5$ when divided by $7$.
$(a,b,c,d)=(6,7,9,10)：10^6+9^7+7^9+5^{10} = 55902201$

Sample 2
Input
5 8 3
1 2 3 5 8
Output
3

The following $3$ tuples $a,b,c,d$ satisfy the condition of leaving a remainder of $3$ when divided by $8$.
$(a,b,c,d)=(1,2,3,8)：10^1+9^2+7^3+5^8 = 391059$
$(a,b,c,d)=(1,2,5,8)：10^1+9^2+7^5+5^8 = 407523$
$(a,b,c,d)=(1,3,4,8)：10^1+9^3+7^4+5^8 = 408171$

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