No.2709 1975 Powers
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 168
作問者 : 👑
Nafmo2
/ テスター :
dyktr_06
sepa38
ryota2357
タグ : / 解いたユーザー数 168
作問者 : 👑
Nafmo2
/ テスター :
dyktr_06
sepa38
ryota2357
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。