8/17 牛客训练营9补题+cf(B、C)

B-Two Frogs

题意：两只青蛙从荷叶1跳到荷叶n，每个荷叶可跳的范围是(i,i+a[i]](左开右闭)，问两只青蛙跳到荷叶n的概率是多少？ 所用知识：前缀和、差分、dp 思路： 1.设计状态dp[i][j]：表示所用j步跳到荷叶i的概率是多少 2.状态的转移：当前青蛙可跳的荷叶数为(i,i+a[i]]，共有a[i]个荷叶可供选择。因此这段区间dp[i+1~i+a[i]][j+1]的概率都为dp[i][j]/a[i]. 3.由此可看出是区间值得累加，因此想到差分。dp[i+1][j+1]加上概率dp[i][j]/a[i]，而dp[i+a[i]+1][j+1]则减去概率dp[i][j]/a[i] 4.在每次对dp[i][j]进行操作时，要写一个for循环进行前缀和得累加。

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i>=1;
    }
    return res;
}

void solve()
{
    cin>>n;
    for(int i=1;i>a[i],b[i]=qpow(a[i],mod-2);
    dp[1][0]=1;
    dp[2][0]=-1;
    for(int i=1;i