NC25193. biubiubiu坐地铁
描述
BiuBiuBiu 每次出去玩都要去坐地铁，BiuBiuBiu 观察到，当地铁上人比较少的时候，大家都会选择那些与其他人不相邻的座位，现在地铁上有 n 个座位排成一排，1 号座位与 2 号相邻，n 号座位与 n-1 号相邻，除了 1 号与 n 号座位，任意 i 号座位都与 i-1 和 i+1 号座位相邻。现在有源源不断的人上车，每次只会有一个人上车，他会在所有的相邻座位没有人的座位中随机选择一个坐下，如果没有满足条件的座位则不会坐下。然后下一个人上车。求最后这辆地铁坐下的人数的期望。
输入描述
输入一个整数n(1<=n<=1000000)。
输出描述
能够证明期望是个分数，所以输出期望模1000000007。
示例1
输入:
3
输出:
666666673
C++11(clang++ 3.9) 解法, 执行用时: 208ms, 内存消耗: 8292K, 提交时间: 2020-05-23 17:57:43
#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define M 1000000007
LL pw(int x,int y){LL i=1,j=x,k=y;while(k){i*=max((k&1)*j%M,(LL)1);i%=M;k>>=1;j=(j*j)%M;}return i;}
LL i,j,k,m,sb[1000110],tmp1,tmp2;
int main(){sb[1]=sb[2]=1;for(i=3;i<=1000000;i++){tmp1=2*pw(i,M-2)%M;tmp2+=sb[i-2];tmp2%=M;sb[i]=tmp1*tmp2%M+1;}scanf("%lld",&m);printf("%lld\n",sb[m]);}