| 题目名称 | 1908. [WC 2014]时空穿梭 |
|---|---|
| 输入输出 | WC2014A.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Asm.Def
于2015-01-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：7， 提交：24， 通过率：29.17% | ||||
 Hzoi_Hugh |
100 | 3.000 s | 123.23 MiB | C++ |
 JSX |
100 | 3.975 s | 113.69 MiB | C++ |
 木留木留木 |
100 | 4.342 s | 113.29 MiB | C++ |
 Asm.Def |
100 | 4.651 s | 121.68 MiB | C++ |
 呵呵酵母菌 |
100 | 5.187 s | 98.07 MiB | C++ |
 Hzoi_Ivan |
100 | 5.315 s | 270.21 MiB | C++ |
 Troywar |
100 | 6.378 s | 186.58 MiB | C++ |
|
呵呵酵母菌 |
60 | 3.952 s | 98.07 MiB | C++ |
|
Troywar |
60 | 5.487 s | 18.72 MiB | C++ |
|
Hzoi_Hugh |
50 | 5.705 s | 17.94 MiB | C++ |
| 关于 时空穿梭 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
感觉整个人都被反演了 #.#
JSX
2015-02-07 06:05
3楼
| ||||
|
TAT终于开始上传WC2014的题了……这是一道莫比乌斯反演题
数论题的特点似乎就是……思维过程极其繁琐，代码却极其简单？反正我推公式推了好久，写出来只有一百多行…… @Chenyao 哪有……这道题我纠结了好几天，期间TLE一次WA三次…… | ||||
|
回复 @Asm.Def :
就一百多行....一百多行....白多行...多行...行... 给屠数论的跪了 Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz  Chenyao2333
2015-01-24 14:29
1楼
| ||||
【题目描述】
小 X 驾驶着他的飞船准备穿梭过一个 n 维空间，这个空间里每个点的坐标可以用 n 个实数表示，即 (x1,x2,…,xn)。
为了穿过这个空间，小 X 需要在这个空间中选取 c（c≥2）个点作为飞船停留的地方，而这些点需要满足以下三个条件：
每个点的每一维坐标均为正整数，且第 i 维坐标不超过 mi。第 i+1（1≤i<c）个点的第 j（1≤j≤n）维坐标必须严格大于第 i 个点的第 j 维坐标。存在一条直线经过所选的所有点。在这个 n 维空间里，一条直线可以用 2n 个实数 p1,p2,…,pn,v1,v2,…,vn 表示。直线经过点 (x1,x2,…,xn)，当且仅当存在实数 t，使得对 i=1…n 均满足 xi=pi+tvi。小 X 还没有确定他的最终方案，请你帮他计算一下一共有多少种不同的方案满足他的要求。由于答案可能会很大，你只需要输出答案 mod 10007 后的值。
【输入格式】
第一行包含一个正整数 T，表示有 T 组数据需要求解。
每组数据包含至少两行行，第一行包含两个正整数 n,c（c≥2），分别表示空间的维数和需要选择的暂停点的个数。
接下来有 n 行，每行一个正整数，依次表示 m1,m2,…,mn。
【输出格式】
共 T 行，每行包含一个非负整数，依次对应每组数据的答案。
【样例输入】
3 2 3 3 4 3 3 3 4 4 4 4 5 9 7 8
【样例输出】
2 4 846
【数据范围】
【来源】
WC2014 A.