Σ?

2 secs 1024 MB
stafx's icon stafx
Tweet
Problem
Submissions
Test cases

次を満たす添字の集合 TT は存在する？

∑j∈T(AjAj mod 109)=S\sum_{j \in T} \left( A_j^{A_j} \bmod 10^9 \right) = S

制約

  • 1≤N≤1071 \le N \le 10^7
  • 1≤Ai≤109−11 \le A_i \le 10^9 - 1
  • 1≤S≤10181 \le S \le 10^{18}
  •  min⁡(2N,S)≤108/N\ \min(2^N, S) \le 10^8 / N

入力

N  N     S  S

A1... AN A_1 ...  A_N  

出力

存在するならYesYes,存在しないならNoNoを出力せよ

入力例1

1 4
2

出力例1

Yes

T=T={1} とすると222^2 = 4 なのでYesを出力します

入力例2

2 314159
2 3

出力例2

No

制作:stafx 8/3 21:27テストケースを修正しました

Submit

Go (1.21)