我们可以把问题变成若干个子问题：有连续T个数字，都在1..L的范围内，要求不下降，问有多少种可能。用F(T,L)表示这一问题。

我们先把T个数字排成一列，加上左右两边就形成了T+1个区间，我们可以把1到L都放到这些区间中，那么对于第i个数字，我们可以就可以选用其左边的区间中最大的数字。所以1一定是放在了最左边的区间中。于是问题变成了给定N+1个连续区间，放入1到L共L-1个数字，要求大的数字一定在小的数字的右边。这个问题在卢开澄的《组合数学》一书中有详细介绍，G(a,b)=C(a+b-l,b).于是F(T,L)=C(T+L-1, L-1)。

这样我们就已经解决了第一问。

对于第二问，我们很明显有这样一个猜想，平均情况就是所有不确定的数字都等于左右最近的确定数字的mid。一个简单的证明是，你可以把不确定的数字水平翻转后看，发现与翻转前是等价的，而二者和的平均数很明显是左右数字的mid,于是结论成立。

但是问题还远没有结束。

对于求C(n,m)我们一般的方法有递归和直接求解。这里n,m过大,最大可以到2*10^6, 所以我们只能直接求解，

\(\frac{n!}{m!(n-m)!}=n!*Inv(m!)*Inv((n-m)!)\)

于是我们可以先预处理出Fac(x)，Inv(x)和ΠInv(x)。

对于Inv(x),我们用快速幂可以在O(xlogMOD)内得到，但是本题这样做是Tle的。 我们考察新的方法。设MOD=kx+b,则

\(x^{MOD-2}=x^{kx+b}=kx*b^{kx+b}\)

，于是我们可以递推在O(N)内求出Inv(1)到Inv(N)。这样初始化的时间复杂度就是O(N)的了，算法的总时间复杂度是O(N+M)。

至此问题顺利解决。最后提及一下，1000000007和1000000009是一对很唯美的孪生质数。

输出有点谜啊
printf("Case #%d: %lld", ++j, ans1);
printf(" %.3lf\n", ans2);
AC
printf("Case #%d: %lld %.3f\n", ++j, ans1, ans2);
WA
自家电脑也这样，难道是蒟蒻自带SB光环？

能发个标程吗？

解答: http://pan.baidu.com/s/1ntJW1jr