CF1810G The Maximum Prefix 题解
典型的反转 ，整理一下此类题思路。
题意简述
你现在要按照如下方式生成一个长度为 的数组：
对于一个长度为 的数组，计算
。特别地，。此时 数组的最大前缀和 。现在给定 个正整数 。该数组最大前缀和为 时，该数组的分数为 。
要求对于所有 ，求出生成出的数组的期望分数对 取模的结果。
。
思路分析
正向考虑困难，因为我们要加入一个新的前缀和，而这个前缀和的值与其前一位前缀和的值相关，所以需要同时存下最大的
和当前的 ，复杂度升天，那么反向考虑。
此时容易发现，我们向一个序列的开头加入一个 或 ，会将之后的所有前缀和 或 ，同时再加入一个新的前缀和。这是相对来说容易转移的。因此，对于某一个
，我们有如下朴素 过程，设 表示数组 的 值为 时的期望分数：
直接进行这个过程，由于需要枚举 ，复杂度是 的，不足以通过此题。
考虑状态所设两维难以压掉，尝试去除枚举 所带来的复杂度。观察 过程，我们共进行了 次 ，而每次
都指向同一组终止状态。因此考虑反转整个
过程，我们从终止状态出发，进行反向转移，最终抵达初始状态。
刚才所设的是“已经”，那么我们可以设“还需要”。具体来说，我们设 表示数组 的 值需要为
的最终数组的期望分数，换句话来说，我们钦定了 的 值为 ， 表示在这样的限制条件下， 的期望分数。那么我们有
， 的答案即为 。有转移：
容易发现与之前的转移形式一致。
此时有可能会产生这样的疑惑：如果仅仅钦定了 的 值为 ，那么有一部分填法中 的 值为 ，另一部分 值为 ，那么为什么 能够同时对 和 做等量的贡献？
这时，考虑
定义。我们此时并不知道
的填法，我们只是要求这一数组的
值为 。那么，如果我们在 处填了 ，无论我们要求 的 值填为 还是 ，都符合我们对
的要求，自然都应该进行转移。
启发
- 前缀和问题，正难则反。
- 多起点单终点问题，考虑反转 。
- 反转
需要明确状态定义。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int p[50005],h[50005],dp[5005][5005];
int qkp(int x,int k){
int ret=1;
while(k){
if(k&1) ret=ret*x%mod;
k>>=1;
x=x*x%mod;
}
return ret;
}
int ny(int x){return qkp(x,mod-2);}
signed main(){
int t,n,x,y;
cin>>t;
while(t--){
scanf("%lld",&n);
for(int i=0;i<=n+1;i++)
for(int j=0;j<=n+1;j++)
dp[i][j]=0;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&x,&y);
p[i]=x*ny(y)%mod;
}
for(int i=0;i<=n;i++) scanf("%lld",&h[i]),dp[0][i]=h[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
dp[i][j]=(p[i]*dp[i-1][j+1]%mod+(1-p[i]+mod)*dp[i-1][max(j-1,0ll)]%mod)%mod;
}
printf("%lld ",dp[i][0]);
}
puts("");
}
return 0;
}
|