学姐的实习工资
描述
学姐去实习了, 一共实习了N天, 每一天都可以得到实习工资V[i], 这里V[1..N]被看作是整数序列.
因为学姐很厉害, 所以V[1..N]是不下降的.
也就是说学姐每天的工资只会越来越多, 不会变少.
然而遗憾的是, 偷懒的学姐只记下来了其中M天的收入.
第A[1]天获得了的工资为B[1].
第A[2]天获得了的工资为B[2].
第A[3]天获得了的工资为B[3].
...
第A[M]天获得了的工资为B[M].
其中A[]是递增的.
好在她记下来了第一天和第N天的收入. 也就是说A[1]=1, A[M]=N.
现在实习结束了, 学姐看着仅有的M天的记录, 希望知道:
(1)工资序列V[1..N]有多少种可能情况, 满足已知的M条记录. 答案mod 1000000009.
(2)平均来说(考虑所有可能的情况), N天中一共得到了多少工资, 答案四舍五入到小数点后第三位.
如果doc不能回答学姐的这两个问题, 学姐会生气的!
格式
输入格式
输入数据第一行给定T, 表示总的询问次数.
对于每一次询问, 第一行给出两个整数N和M.
第二行给出M个整数, 分别为A[1]到A[M].
第三行给出M个整数, 分别为B[1]到B[M].
输出格式
对于每一次询问, 首先输出询问的编号, 参见样例输出.
之后输出问题1和问题2的答案, 用空格隔开, 详细请参见样例输出.
样例1
样例输入1
2
6 5
1 2 3 5 6
3 5 10 20 20
6 6
1 2 3 4 5 6
3 5 10 15 20 20
样例输出1
Case #1: 11 73.000
Case #2: 1 73.000
限制
对于30%的数据:
N <= 100.
对于60%的数据:
N <= 50000.
对于100%的数据:
2 <= N <= 1000000.
M <= 1000.
T <= 10.
1 = A[1] < A[2] < ... < A[M] = N.
0 <= B[1] <= B[2] <= ... <= B[M] <= 1000000.
信息
- ID
- 1903
- 难度
- 8
- 分类
- (无)
- 标签
- (无)
- 递交数
- 158
- 已通过
- 13
- 通过率
- 8%
- 被复制
- 4
- 上传者