海亮 7.24 水题选讲

海亮 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;
}