[CF1810G] The Maximum Prefix

题目描述

You're going to generate an array $ a $ with a length of at most $ n $ , where each $ a_{i} $ equals either $ 1 $ or $ -1 $ .

You generate this array in the following way.

• First, you choose some integer $ k $ ( $ 1\le k \le n $ ), which decides the length of $ a $ .
• Then, for each $ i $ ( $ 1\le i \le k $ ), you set $ a_{i} = 1 $ with probability $ p_{i} $ , otherwise set $ a_{i} = -1 $ (with probability $ 1 - p_{i} $ ).

After the array is generated, you calculate $ s_{i} = a_{1} + a_{2} + a_{3}+ \ldots + a_{i} $ . Specially, $ s_{0} = 0 $ . Then you let $ S $ equal to $ \displaystyle \max_{i=0}^{k}{s_{i}} $ . That is, $ S $ is the maximum prefix sum of the array $ a $ .

You are given $ n+1 $ integers $ h_{0} , h_{1}, \ldots ,h_{n} $ . The score of an array $ a $ with maximum prefix sum $ S $ is $ h_{S} $ . Now, for each $ k $ , you want to know the expected score for an array of length $ k $ modulo $ 10^9+7 $ .

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 5000 $ ) — the number of test cases. Their description follows.

The first line contains an integer $ n $ ( $ 1\le n \le 5000 $ ).

Then for the following $ n $ lines, each line contains two integers $ x_{i} $ and $ y_{i} $ ( $ 0 \le x_{i} < 10^9 + 7 $ , $ 1\le y_{i} < 10^9 + 7 $ , $ x_{i} \le y_{i} $ ), indicating $ p_{i} = \frac{x_{i}}{y_{i}} $ .

The next line contains $ n+1 $ integers $ h_{0},h_{1}, \ldots, h_{n} $ ( $ 0 \le h_{i} < 10^9 + 7 $ ).

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ .

蠢题，我更蠢。

最大值看起来很难处理。

有一个暴力：枚举最大值，定义 \(dp_{i,j，0/1}\) 为目前到 \(i\) 前缀和为 \(j\)，目前是否达到过，复杂度 \(O(n^3)\)

考虑优化，把他们放在一起 dp. 定义 \(dp_{i,j,0/1}\) 为现在在 \(i\)，离上限差 \(j\) ，是否到达过上界。

#include<bits/stdc++.h>
using namespace std;
const int P=1e9+7,N=5005;
int pown(int x,int y)
{
	if(!y)
		return 1;
	int t=pown(x,y>>1);
	if(y&1)
		return 1LL*t*t%P*x%P;
	return 1LL*t*t%P;
}
int read()
{
	int s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s;
}
int dp[N][N][2],n,T,p[N];
int main()
{
	T=read();
	while(T--)
	{
		n=read();
		for(int i=1,x,y;i<=n;i++)
			x=read(),y=read(),p[i]=1LL*x*pown(y,P-2)%P;
		dp[0][n+1][0]=dp[0][n+1][1]=0;
		for(int i=0;i<=n;i++)
			dp[0][i][!i]=read();
		for(int i=1;i<=n;i++)
		{
			dp[i][n+1][0]=dp[i][n+1][1]=0;
			int ans=0;
			for(int j=0;j<=n;j++)
			{
				if(j)
				{
					dp[i][j][0]=(dp[i-1][j-1][0]*(1LL+P-p[i])+dp[i-1][j+1][0]*1LL*p[i])%P;
					dp[i][j][1]=(dp[i-1][j-1][1]*(1LL+P-p[i])+dp[i-1][j+1][1]*1LL*p[i])%P;
				}
				else
					dp[i][j][1]=(dp[i-1][j+1][0]+dp[i-1][j+1][1])*1LL*p[i]%P,dp[i][j][0]=0;
				(ans+=dp[i][j][1])%=P;
				//printf("%d %d %d %d\n",i,j,dp[i][j][0],dp[i][j][1]);
			}
			printf("%d ",ans);
		}
		puts("");
	}
}