题目描述
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("");
}
}