解题思路

一次选取是同频的，当且仅当被选中的每个下标 $i$ 都满足 $p_i+q_i$ 相同。因此，不同的和值之间互不影响，方案可以按和值分组后分别计数再相加。

用哈希表统计每个和值 $s = p_i + q_i$ 出现的次数 $\mathrm{cnt}(s)$ 。对固定的 $s$ ，该组内任意非空下标子集都合法，方案数为

2^{\mathrm{cnt}(s)}-1

把所有和值的方案数加起来，并对 $10^9+7$ 取模。快速幂计算 $2^{\mathrm{cnt}}$ 即可。注意减去 1 时要先加上模数再取模，避免出现负数。

题目内容

实验室同时记录了两路长度为 $n$ 的采样序列 $p$ 和 $q$ 。从全部下标中选出一个非空集合，按下标递增顺序取出对应位置上的数值，会得到两个等长的新序列。

称这次选取是同频的，当且仅当被选中的每一个下标 $i$ 都满足： $p_i + q_i$ 的值全部相同。

请计算有多少种不同的非空同频选取方案。答案可能很大，输出对 $10^9+7$ 取模后的结果。

约束条件：

选择提交后点击「开始AI分析」