問題一覧 > 通常問題

No.2709 1975 Powers

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 148
作問者 : 👑 Nafmo2Nafmo2 / テスター : dyktr_06dyktr_06 sepa38sepa38 ryota2357ryota2357
2 ProblemId : 9986 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-27 14:45:41

問題文

$N$ 個 の整数からなる数列 $A = (A_1,A_2,\dots,A_N)$ があります.

$A$ から 異なる $4$ つの整数 $a,b,c,d$ を選ぶ方法のうち,以下の条件を満たす選び方は何通りあるかを求めてください.

  • $10^a+9^b+7^c+5^d$ が $P$ で割ったとき $Q$ 余る
  • $a < b < c < d$

入力

$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)$
  • 入力はすべて整数

出力

条件を満たす4つの整数の選び方が何通りかを求めて出力してください.

サンプル

サンプル1
入力
5 7 5
7 3 9 6 10
出力
1

$a,b,c,d$ の組が以下の時のみ $7$ で割ったとき $5$ 余る条件を満たす.
$(a,b,c,d)=(6,7,9,10):10^6+9^7+7^9+5^{10} = 55902201$

サンプル2
入力
5 8 3
1 2 3 5 8
出力
3

以下の $3$ つの $a,b,c,d$ の組が $8$ で割ったとき $3$ 余る条件を満たす.
$(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もしくは右上の雲マークをクリックしてアカウントを作成してください。