题目
题解
1.我会暴力：
时间复杂度 O(2^n) ，必定TLE
2.我会正解：
我们看一下题目，可以想到一个思路：将数组截成两半，分别暴力，将结果排序，最后统计答案。
如何统计答案？
我们设前半部分所有可能性为 sum1 ，后半部分为 sum2 ，则可以依次取出 sum1 中每个数 i ，并求解 i*j \mod p \equiv c|j\in sum2 的对的个数
蛋柿正解不可能直接暴力枚举，肯定要先拆式子
i\times j \bmod p=c \\
=>i\times j\equiv c(\bmod p)\\
=>i \equiv \dfrac{c}{j}(\bmod p)\\
=>i \equiv c\times j^{-1}(\bmod p)
所以我们预处理出 sum1 中每个数在 \bmod p 意义下的乘法逆元(不知道乘法逆元的点这里)，再使用二分查找左右边界，累加数量，就可以AC了……吗？
当然不是，这题有个小坑：小B记得他至少取了一个数。，所以还需剔除空集的情况。
some code:
sort(sum2.begin(), sum2.end());
for (int &i : sum1)
{
i = get(i);
}
int ans = 0;
for (int i : sum1)
{
int r = upper_bound(sum2.begin(), sum2.end(), c * i % mod) - sum2.begin() - 1;
int l = lower_bound(sum2.begin(), sum2.end(), c * i % mod) - sum2.begin();
ans += (1 + r - l);
ans %= 1000000007;
}
if (1 % mod == c)
{
ans--;//去除空集
}
cout << ans % 1000000007;
upd:
有一个很坑的点： p \le c 时要直接输0