P11682 [Algo Beat Contest 001 D] Dreamed Sequence
题目背景
| Problem | Score | Idea | Std | Data | Check | Solution |
| :---------------------------------: | :---: | :---------------------------------------------------: | :----------------------------------------------------------: | :---------------------------------------------: | :----------------------------------------------------------: | :----------------------------------------------------------: |
| $\text{D - Dreamed Sequence}$ | $425$ | [orchardist](https://www.luogu.com.cn/user/347582) | [orchardist](https://www.luogu.com.cn/user/347582) | [joe_zxq](https://www.luogu.com.cn/user/623577) | [fcy20180201](https://www.luogu.com.cn/user/866154) | [Link](https://www.luogu.com.cn/article/8ibxe6et) by [joe_zxq](https://www.luogu.com.cn/user/623577) |
题目描述
给定长度为 $N$ 的序列 $A$ 和 $B$。
定义 $A$ 和 $B$ 两序列相乘 $A\times B$ 的规则如下，其中模数 $M=10^9+7$：
* 设 $A$ 序列为 $\{A_1,A_2,\dots,A_N\}$，$B$ 序列为 $\{B_1,B_2,\dots,B_N\}$，则相乘得到的序列为 $\{A_1B_1 \bmod M,A_2B_2 \bmod M,\dots,A_NB_N \bmod M\}$。
数学家小 G 梦想着让 $A\times B$ 得到的序列中出现次数最多的数出现的次数尽可能大。为了实现这一点，小 G 可以将 $B$ 数组任意重排列。小 G 想知道，出现次数最多的数最多出现多少次。
请你帮小 G 找到他梦想中的序列。如果小 G 获得了诺贝尔数学奖，他将会与你分享奖金。
输入格式
无
输出格式
无
说明/提示
#### 样例解释 #1
重排 $B$ 序列得 $\{8,4,5,2,6\}$，此时 $A\times B$ 得到的数组为 $\{8,8,15,8,30\}$，其中 $8$ 出现次数最多，出现 $3$ 次。
可以证明不存在重排 $B$ 序列的方式，使得答案大于 $3$。
#### 数据范围
对于 $100\%$ 的数据，保证 $1 \le N \le 2000$，$1 \le A_i,B_i \le 10^9$。