海亮 7.24 水题选讲
The Maximum Prefix
我们设定一个状态 \(f_{i,j}\) 表示这个序列的 \([i+1,n]\) 区间的最大前缀和为 \(j\)，这个序列的期望得分。
转移为 \(f_{i,j}=f_{i-1,j+1}\times p_i+f_{i-1,\max\left(j-1,0\right)}\times\left(1-p_i\right)\)。
第一个整式表示第 \(i\) 个数选 \(1\)，第二个整式表示选 \(-1\)。
初始化即 \(f_{0,i}=h_i\)。
这个状态和方程不难得到，主要考虑如何计算答案。
首先长度为 \(n\) 的答案肯定为 \(f_{n,0}\)。
考虑长度为 \(k\) 的答案，其中 \(1\le k < n\)。
我们发现你构造出来的长度为 \(k\) 的序列其实等价于 \([k+1,n]\) 这个区间对前面没有贡献，即这个区间的最大前缀和为 \(0\)。所以答案为 \(k\) 的答案即为 \(f_{k,0}\)。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
constexpr int N = 5000 + 5;
constexpr int mod = 1e9 + 7;
//char buf[1<<22] , *p1 , *p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
#define getchar() cin.get()
int read ()
{
int x = 0 , f = 1;
char ch = getchar();
while ( !isdigit ( ch ) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit ( ch ) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , f[N][N] , q[N] , p[N];
int ksm ( int base , int k )
{
int res = 1;
while ( k )
{
if ( k & 1 ) res = res * base % mod;
base = base * base % mod;
k >>= 1;
}
return res;
}
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int T = read();
while ( T -- )
{
memset ( f , 0 , sizeof f );
n = read();
for ( int i = 1 , x , y ; i <= n ; i ++ )
x = read() , y = read() , p[i] = x * ksm ( y , mod - 2 ) % mod , q[i] = ( 1 - p[i] + mod ) % mod;
for ( int i = 0 ; i <= n ; i ++ ) f[0][i] = read();
for ( int i = 1 ; i <= n ; i ++ )
for ( int j = 0 ; j <= n ; j ++ ) f[i][j] = ( f[i-1][j+1] * p[i] % mod + f[i-1][max(j-1,0ll)] * q[i] % mod ) % mod;
for ( int i = 1 ; i <= n ; i ++ ) cout << f[i][0] << ' ';
cout << endl;
}
return 0;
}