| 题目名称 | 3170. The Battle of Chibi |
|---|---|
| 输入输出 | Chibi.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 4 |
| 题目来源 |
 LGLJ
于2019-06-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：8， 提交：18， 通过率：44.44% | ||||
 郑霁桓 |
100 | 0.409 s | 10.70 MiB | C++ |
|
梦那边的美好ET |
100 | 0.452 s | 7.07 MiB | C++ |
 Hale |
100 | 0.665 s | 21.39 MiB | C++ |
 LGLJ |
100 | 0.780 s | 5.48 MiB | C++ |
|
liuyiche |
100 | 1.377 s | 10.80 MiB | C++ |
|
liuyiche |
100 | 1.442 s | 10.80 MiB | C++ |
|
liuyiche |
100 | 1.446 s | 10.80 MiB | C++ |
 Satoshi |
100 | 1.935 s | 38.31 MiB | C++ |
|
郑霁桓 |
75 | 0.424 s | 10.70 MiB | C++ |
|
liuyiche |
75 | 1.319 s | 10.79 MiB | C++ |
| 关于 The Battle of Chibi 的近10条评论(全部评论) |
|---|
【题目描述】
给定一个长度为 $N$ 的序列 $A$ ,求 $A$ 有多少个长度 $M$ 的严格递增子序列。
有多组测试数据。
因为答案可能很大，你只需要输出对$10^9+7$取模后的结果。
【输入格式】
第一行 测试数据个数 $T$
每一组测试数据第一行为 $N$ 和 $M$
第二行$N$个整数，表示序列$A_i$
【输出格式】
对于每个测试数据输出
Case #x: y
表示第 $x$ 组测试数据，答案为 $y$
【样例输入】
2 3 2 1 2 3 3 2 3 2 1
【样例输出】
Case #1: 3 Case #2: 0
【提示】
$1<=T<=666$
(数据很水，非官方数据，可以理解为T<=100)
正解时间复杂度为(TNMlogN)
$1<=M<=N<=1000$
$0<=|A_i|<=10^9$
【来源】
《算法竞赛进阶指南》 Uva 12983