#1748. 随机游走

    ID: 1748 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1090来源:qoj.ac数据:公开样例数学

随机游走

随机游走

题目描述

标题: 随机游走 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

小 W 是随机大师,他特别喜欢随机化算法。

这一天,小 W 站在原点 (0,0) 开始了他的随机游走。

每一次,小 W 会选择一个等概率均匀随机的向量 (x,y),使得 x,y∈R,|x|+|y|≤1。之后他会恰好沿着向量移动一次,即若当前坐标为 (A,B),小 W 会移动到 (A+x,B+y)。

小 W 总共会进行 n 次上述的游走操作。在结束所有 n 次操作后,小 W 会结束这次游走。

小 W 对游走的结果很感兴趣,现在他想要知道,在结束游走时,他离 y 轴距离的期望到底是多少。也就是,设结束时的坐标为 (A,B),你需要求出 |A| 的期望大小。

由于答案的表达式可能非常的复杂,你只需要输出答案对质数 p=1000000007 (109+7) 取模的结果即可。

输入格式

一行一个正整数 n,表示小 W 进行的操作次数。

输出格式

一行一个正整数,表示答案对质数 p=1000000007 (109+7) 取模的结果。

可以证明对于所有输入,答案总可以表示成 xy (y≢0(modp)) 的形式,此时你只需要输出 (x×yp−2)modp 的结果即可。

样例数据

样例 1 输入

1

样例 1 输出

333333336

样例 1 解释

对于样例 1,答案等于 ∫01x2dx=13。

样例 2 输入

3

样例 2 输出

769047625

样例 2 解释

对于样例 2,答案等于 239420。

数据范围

测试包 1(5%):n≤3;

测试包 2(10%):n≤10;

测试包 3(10%):n≤30;

测试包 4(15%):n≤200;

测试包 5(15%):n≤2000;

测试包 6(15%):n≤2×105;

测试包 7(30%):n≤5×106。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1
333333336

样例 2

3
769047625