#1748. 随机游走
随机游走
随机游走
题目描述
标题: 随机游走 - Problem - QOJ.ac
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