seuOJ9180 - (i,j)-可分数列问题

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：512 MiB
• 题目标签：
• 存在附加文件

题目描述

设 $k,m$ 为正整数，数列 $a_1,a_2,\cdots,a_{km+2}$ 是公差不为 $0$ 的等差数列，若从中删去两项 $a_i$ 和 $a_j$（$i\lt j$）后剩余的 $km$ 项可被平均分为 $m$ 组，且每组的 $k$ 个数都能构成等差数列，则称数列 $a_1,a_2,\cdots,a_{km+2}$ 是 $(i,j)$-可分数列。

以 $k=4,m=3$ 为例，$a_1,a_2,\cdots,a_{14}$ 是 $(2,13)$-可分数列，因为从中删去两项 $a_2$ 和 $a_{13}$ 后剩余的 $12$ 项可被平均分为 $3$ 组——$\{a_1,a_4,a_7,a_{10}\}$、$\{a_3,a_6,a_9,a_{12}\}$ 和 $\{a_5,a_8,a_{11},a_{14}\}$，且每组的 $4$ 个数都能构成等差数列。

从 $1,2,\cdots,km+2$ 中一次任取两个数 $i$ 和 $j$（$i\lt j$），记数列 $a_1,a_2,\cdots,a_{km+2}$ 是 $(i,j)$-可分数列的概率为 $P_{k,m}$。例如，$P_{4,1}=\dfrac{3}{\binom{6}{2}}=\dfrac{1}{5}$。

给定 $k,Q$ 和 $m_1,m_2,\cdots,m_Q$，求 $P_{k,m_1},P_{k,m_2},\cdots,P_{k,m_Q}$。

请输出答案对 $10^9 +7$ 取模的结果。形式化地，答案能被表示为最简分数 $\dfrac{p}{q}$，请输出 $x$ 满足 $0\le x\lt10^9+7$ 且 $qx\equiv p\pmod{10^9+7}$，在题目条件下这样的 $x$ 唯一存在。

输入格式

第一行两个整数 $k,Q$。

第二行 $Q$ 个整数 $m_1,m_2,\cdots,m_Q$。

输出格式

一行 $Q$ 个整数 $P_{k,m_1},P_{k,m_2},\cdots,P_{k,m_Q}$，对 $10^9+7$ 取模。

样例

输入

4 2
1 114514

输出

400000003 372952430

数据范围与提示

对于 $100\%$ 的数据，$1\le k\le300$，$1\le Q\le2024$，$1\le m_i\le10^8$。

Source：2024 年新高考 I 卷数学 T19 加强

❤ Powered by LgxCute ❤