UOJ Logo Universal Online Judge

UOJ

#54. 【WC2014】时空穿梭

附件下载 统计

小 X 驾驶着他的飞船准备穿梭过一个 $n$ 维空间,这个空间里每个点的坐标可以用 $n$ 个实数表示,即 $(x_1, x_2, \dots, x_n)$。

为了穿过这个空间,小 X 需要在这个空间中选取 $c$($c \geq 2$)个点作为飞船停留的地方,而这些点需要满足以下三个条件:

  1. 每个点的每一维坐标均为正整数,且第 $i$ 维坐标不超过 $m_i$。
  2. 第 $i + 1$($1 \leq i < c$)个点的第 $j$($1 \leq j \leq n$)维坐标必须严格大于第 $i$ 个点的第 $j$ 维坐标。
  3. 存在一条直线经过所选的所有点。在这个 $n$ 维空间里,一条直线可以用 $2n$ 个实数 $p_1, p_2, \dots, p_n, v_1, v_2, \dots, v_n$ 表示。直线经过点 $(x_1, x_2, \dots, x_n)$,当且仅当存在实数 $t$,使得对 $i = 1 \dots n$ 均满足 $x_i = p_i + tv_i$。

小 X 还没有确定他的最终方案,请你帮他计算一下一共有多少种不同的方案满足他的要求。由于答案可能会很大,你只需要输出答案 $\bmod 10007$ 后的值。

输入格式

第一行包含一个正整数 $T$,表示有 $T$ 组数据需要求解。

每组数据包含两行,第一行包含两个正整数 $n, c$($c \geq 2$),分别表示空间的维数和需要选择的暂停点的个数。

第二行包含 $n$ 个正整数,依次表示 $m_1, m_2, \dots, m_n$。

输出格式

共 $T$ 行,每行包含一个非负整数,依次对应每组数据的答案。

样例一

input

3
2 3
3 4
3 3
3 4 4
4 4
5 9 7 8

output

2
4
846

explanation

对于第一组数据,共有两种可行的方案:一种选择 $(1, 1), (2, 2), (3, 3)$,另一种选择 $(1, 2), (2, 3), (3, 4)$。

样例二

见样例数据下载。

限制与约定

测试点编号$T$$n$$c$$m_i$
1$= 1000$$= 1$$\leq 20$$\leq 100000$
2$= 3$$\leq 4$$\leq 20$$\leq 30$
3$= 3$$= 2$$= 3$$\leq 100000$
4$= 1000$$= 2$$= 3$$\leq 100000$
5$= 20$$\leq 5$$= 3$$\leq 100000$
6$= 100$$\leq 11$$= 3$$\leq 100000$
7$= 1$$\leq 5$$\leq 20$$\leq 100000$
8$= 20$$\leq 5$$\leq 20$$\leq 100000$
9$= 100$$\leq 11$$\leq 20$$\leq 100000$
10$= 100$$\leq 11$$\leq 20$$\leq 100000$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载