問題一覧 > 通常問題

No.2709 1975 Powers

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

問題文

NN 個 の整数からなる数列 A=(A1,A2,…,AN)A = (A_1,A_2,\dots,A_N) があります．

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

  • 10a+9b+7c+5d10^a+9^b+7^c+5^d が PP で割ったとき QQ 余る
  • a<b<c<da < b < c < d

入力

N P QN \ P \ Q
A1 A2 … ANA_1 \ A_2 \ \dots \ A_N
  • 4≤N≤2004 \leq N \leq 200
  • 2≤Q<P≤1052 \leq Q < P \leq 10^5
  • 1≤Ai≤2×1061 \leq A_i \leq 2 \times 10^6
  • Ai≠Aj (i≠j)A_i \neq A_j \ (i \neq j)
  • 入力はすべて整数

出力

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

サンプル

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

a,b,c,da,b,c,d の組が以下の時のみ 77 で割ったとき 55 余る条件を満たす．
(a,b,c,d)=(6,7,9,10)：106+97+79+510=55902201(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

以下の 33 つの a,b,c,da,b,c,d の組が 88 で割ったとき 33 余る条件を満たす．
(a,b,c,d)=(1,2,3,8)：101+92+73+58=391059(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)：101+92+75+58=407523(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)：101+93+74+58=408171(a,b,c,d)=(1,3,4,8)：10^1+9^3+7^4+5^8 = 408171

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