CF1810G The Maximum Prefix

Ecrade_ · 2023-06-19 15:33:23 · 题解

分享一种理解起来可能更为简单的思路。

假设我们钦定了 a 数组的最大前缀和为 x，那么 a 的前缀和数组 s 需要满足：

形象地，我们称这个钦定的最大前缀和 x 为 “目标”。令 f_{i,j,0/1} 表示仅考虑前 i 个元素，当前前缀和 s_i 离目标还差 j，之前达到过 / 未达到过目标的期望得分。则对于长度 i，其答案即为当前所有达到过目标的状态的期望得分之和。

初始化：f_{0,i,[i=0]}=h_i。

转移方程：f_{i,j,o\ |\ [j=0]}=f_{i-1,j+1,o}\times p_i+f_{i-1,j-1,o}\times (1-p_i)。

长度为 k 时的答案：\sum\limits_{i=0}^nf_{k,i,1}。

注意处理边界问题，具体见代码。

时间复杂度为 O(n^2)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int t,n,x,y,p[5009],f[5009][5009][2];
inline int read(){
    int s = 0,w = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
    while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    return s * w;
}
inline void add(int &x,int y){x += y; if (x >= mod) x -= mod;}
int qp(int x,int y){
    int a = 1,b = x;
    while (y){
        if (y & 1) a = (ll) a * b % mod;
        b = (ll) b * b % mod,y >>= 1;
    }
    return a;
}
int main(){
    t = read();
    while (t --){
        n = read();
        for (int i = 1;i <= n;i += 1) x = read(),y = read(),p[i] = (ll) x * qp(y,mod - 2) % mod;
        for (int i = 0;i <= n;i += 1) f[0][i][!i] = read();
        for (int i = 1;i <= n;i += 1){
            int ans = 0;
            for (int j = 0;j <= n;j += 1){
                f[i][j][0] = f[i][j][1] = 0;
                for (int o = 0;o < 2;o += 1){
                    if (j < n) add(f[i][j][o | (!j)],(ll) f[i - 1][j + 1][o] * p[i] % mod);
                    if (j > 0) add(f[i][j][o | (!j)],(ll) f[i - 1][j - 1][o] * (mod + 1 - p[i]) % mod);
                }
                add(ans,f[i][j][1]);
            }
            printf("%d ",ans);
        }
        puts("");
    }
    return 0;
}