CF1009E

· · 题解

前言：笔者刚脱离高考深海，正在复健，因此题解可能详细到了啰嗦的地步，比较适合和笔者一样的复健人或者基础不好或完全不懂人。

提供一个粗暴的 DP 写法。

令初始位置标号为 1，设走到位置 i 时所有走法的代价的期望之和为 dp_i，下面对转移方程的推导只需要高中理科数学知识：

首先注意，按照题目定义，a 数组是具体地每一步的代价，题目中的意思其实就是连续走的第 s 步代价是 a_s，注意，参照常识，这里显然没有对第 0 步进行定义。那么，连续走若干步的总代价是 a 数组的前缀和，建立前缀和数组 s，即 s_i=\sum_{j=1}^{i}a_j。

之后，考虑转移：这种线性模型题显然是分段模型，前继状态清晰——所有有可能的上次的位置，显然是个前缀；附加贡献清晰——从前继状态走到当前位置的位移长度的期望。本身看着不太难，大概一写方程就会发现有点复杂。

如果有写过高中数学题的经验，期望之间直接搞是很难算的，由于期望在这种离散情景下不严谨地可以说是用概率和实际值的积定义的，可以在转移的时候把式子拆回这两个层面。

考虑概率，之前的每一步都有可能休息，设此时走了 s 步，那么休息方式的数量等同于大小为 s 的集合的子集个数（包含自身与空集，对应一步一歇和打死不歇的情况），为 2^s （若不知道请补习高中数学集合论部分，推不出来顺便补习加法原理与乘法原理），注意最开始的 DP 状态定义的下标是位置，从初始位置走到当前位置的步数为当前位置标号减一。可见，知道位移就可以在常数时间或次常数时间复杂度内算出概率。

实际值的话，一段位移的贡献是区间和，前继状态是期望值，算出来实际值也很简单：将其视作从初始位置到前继下标位置的位移，知道位移就知道步数，概率也就能算出来，直接除下去就是。

注意这里还有一个坑：状态定义是期望和，转化成实际值是所有实际值的和，位移贡献一次一般是不够的（除非可能性只有一种），需要对每个可能性都产生贡献，也就是说，位移对状态实际值的贡献是位移长度与该状态包含的可能性个数之积（说通俗一点，方案数），后者显然是概率的倒数。

现在，推出方程：如果没有前继，也就是直接从初始位置走，位移为 i，贡献的期望是 \frac{s_{i}}{2^{i-1}}；否则，设前继状态为 dp_j，其贡献转化为实际值为 \frac{dp_j}{\frac{1}{2^{j-1}}}=dp_j \times 2^{j-1}，从前继走到当前位置的位移为 i-j+1,步数为 i-j，实际值为 s_{i-j}，前继包含方案数按上文为 2^{j-1}，则位移的贡献为 s_{i-j}\times 2^{j-1}，该前继贡献的实际值为 dp_{j}\times 2^{j-1}+s_{i-j}\times 2^{j-1}，转为期望值为 \frac{dp_{j}\times 2^{j-1}+s_{i-j}\times 2^{j-1}}{2_{i-1}}。

综上，考虑所有前继，可得出转移方程：

dp_{i}=\frac{s_{i}}{2^{i-1}}+\sum_{j=1}^{i-1}\frac{dp_{j}\times 2^{j-1}+s_{i-j}\times 2^{j-1}}{2_{i-1}}

复杂度看起来非常平方，这里用一些手法把 DP 过程本身优化到线性或次线性复杂度：

把式子后半截那一堆分数拆开整理一下：

\sum_{j=1}^{i-1}\frac{dp_{j}\times 2^{j-1}+s_{i-j}\times 2^{j-1}}{2^{i-1}} =\sum_{j=1}^{i-1}(\frac{dp_{j}\times 2^{j-1}}{2^{i-1}}+\frac{s_{i-j}\times 2^{j-1}}{2^{i-1}}) =\sum_{j=1}^{i-1}(\frac{dp_{j}\times 2^j}{2^i}+\frac{s_{i-j}}{2^{i-j}})

注意：在这里求和的遍历过程内，j 与 i-j 的区别仅在于遍历顺序，对总的结果无影响，因此，进一步转化，得：

\sum_{j=1}^{i-1}(\frac{dp_{j}\times 2^j}{2^i}+\frac{s_{j}}{2^j}) =\sum_{j=1}^{i-1}\frac{dp_{j}\times 2^j}{2^i}+\sum_{j=1}^{i-1}\frac{s_{j}}{2^j}

令 s1_i=\sum_{j=1}^{i}{dp_{j}\times 2^j}，s2_i=\sum_{j=1}^{i}\frac{s_{j}}{2^j}，二者均可以通过前缀和递推完成计算，此时转移方程为

dp_i=\frac{s_{i}}{2^{i-1}}+\frac{s1_{i-1}}{2^{i}}+{s2}_{i-1}

初始状态显然为 dp_0=0，注意取模和逆元处理。

总复杂度为 \Theta(n\log p+n) ,p=998244353，瓶颈在于逆元预处理用了快速幂。

Code：（去掉那几行注释挺短的。注释给自己写的，主要是写的时候提醒自己。）

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+1,DLA=998244353;
ll a[N],s[N],tp[N],tpinv[N],n,s1[N],s2[N];
ll dp[N];
ll fpm(ll x,ll y)
{
    ll ans=1;x=x%DLA;
    for(;y;y>>=1,x=(x*=x)%DLA) if(y&1) ans=(ans*=x)%DLA;
    return ans;
}
//dp[i]=s[i]*inv(2^(i-1))+/sum (dp[j]+s[i-j])*(2^(j-1))*inv(2^(i-1))
//j=1,j<=i-1
//dp[i]=s[i]*inv(2^(i-1))+/sum (dp[j]+s[i-j])*inv(2^(i-j))
//后半部分求和式：把期望乘上概率（已知）还原成实际值，之后除回去
//s[i-j]也要乘，因为还原成实际值后，所有的情况都要加一份s[i-j]
//注意i-j与j在1到i-1上对称
//dp[i]=s[i]*inv(2^(i-1))+/sum (dp[j]*2^j)*inv(2^i) +/sum s[j]*inv(2^(j))
//前缀和处理sum (dp[j]*2^j)与sum s[j]*inv(2^(j))
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;tp[0]=1;
    for(auto i=1;i<=n;++i) cin>>a[i],s[i]=(s[i-1]+a[i])%DLA,
    tp[i]=(tp[i-1]*2)%DLA;
    for(int i=0;i<=n;++i) tpinv[i]=fpm(tp[i],DLA-2);
    for(int i=1;i<=n;++i) s2[i]=(s2[i-1]+s[i]*tpinv[i]%DLA)%DLA;
    for(auto i=1;i<=n;++i) dp[i]=(s[i]*tpinv[i-1]+s1[i-1]*tpinv[i]+s2[i-1])%DLA,s1[i]=(s1[i-1]+dp[i]*tp[i]%DLA)%DLA;
    cout<<(dp[n]*tp[n-1])%DLA;return 0;
}