求教一道dp

BiuBiuBiu 每次出去玩都要去坐地铁，BiuBiuBiu 观察到，当地铁上人比较少的时候，大家都会选择那些与其他人不相邻的座位，现在地铁上有 n 个座位排成一排，1 号座位与 2 号相邻，n 号座位与 n-1 号相邻，除了 1 号与 n 号座位，任意 i 号座位都与 i-1 和 i+1 号座位相邻。现在有源源不断的人上车，每次只会有一个人上车，他会在所有的相邻座位没有人的座位中随机选择一个坐下，如果没有满足条件的座位则不会坐下。然后下一个人上车。求最后这辆地铁坐下的人数的期望。

原题链接：https://ac.nowcoder.com/acm/contest/642/M

以下为题解，想问一下为什么f[i]=(i+2*cnt)*ksm(i,mod-2)%mod;这一步需要乘以ksm(i, mod-2)？乘以ksm(i,mod - 2) 是什么意思？

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll f[1000100];
int n;
ll ksm(ll x,ll y)
{
        ll res=1;
        while(y)
        {
                if(y&1) res=res*x%mod;
                y>>=1;
                x=x*x%mod;
        }
        return res;
}
int main()
{
       
        f[1]=1;f[2]=1;
        ll cnt=1;
        for(int i=3;i<=1000000;i++)
        {
                f[i]=(i+2*cnt)*ksm(i,mod-2)%mod;
                cnt+=f[i-1];
                cnt%=mod;
        }
        while(~scanf("%d",&n)) printf("%lld\n",f[n]);
        return 0;
}

咫尺天涯2121 发表于 2020-08-21 14:51:50
十分感谢！这道题是我根据面经找到的，估计普通面试的话大概只需要正常求期望，不需要做mod啦，十分感谢你的解答！昨天问了一圈也没人知道到底是在干嘛hhh

现在面经这么难的吗？。。我是转码选手，不过我以前是奥数选手，所以知道这个定理。我能看懂，让我写我根本想不到啊。。

这个命名令人汗颜。看起来是快速幂的意思。这里其实取mod需要用到费马小定理。。https://blog.csdn.net/godleaf/article/details/79844074
原因就是f[n]算的是在n个座位的时候，所产生的总数，但是因为要求期望，我们还需要除以n，因为当前这一步有n种选择（更准确的说是开始第一步）。
除以n的话，也就是循环里面的i，相当于对i^(-1)取mod，应用费马小定理，可以得到i^(-1) mod p = i ^ (p - 2) mod p。上面那个辅助函数，ksm就是快速幂的拼音。这命名。。。
快速幂就是按位，每一位对应的幂乘起来。。
P.S. ： 我不太懂啊，不搞数奥或者ACM的人需要用到这些吗。。。

不知道小帅 发表于 2020-8-21 23:15
这个命名令人汗颜。看起来是快速幂的意思。这里其实取mod需要用到费马小定理。。https://blog.csdn.net/god ...

十分感谢！这道题是我根据面经找到的，估计普通面试的话大概只需要正常求期望，不需要做mod啦，十分感谢你的解答！昨天问了一圈也没人知道到底是在干嘛hhh

不知道小帅 发表于 2020-8-22 06:37
现在面经这么难的吗？。。我是转码选手，不过我以前是奥数选手，所以知道这个定理。我能看懂，让我写我根 ...

不是啦，面经就只有n个座位，人们陆续坐下，不可以挨着坐，求坐下人数的期望这样。但我搜到这个题看完这个答案没看懂，以为后边求mod那边也必须要掌握。这个题貌似是竞赛的题。