依次求每一段公里的期望消耗即可，这是可以递推的
dp[i]表示每公里的期望消耗 dp[i]=1/2*a1+1/4*a2 +...+1/2^(i-1)*ai-1 + 1/2^(i-1)*ai注意最后一项是没有间断的道路的期望虽然是算期望，但是实际上是算概率概率从1到n递推即可
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn = 1e6+10; const ll mod = 998244353; int n; ll a[maxn],dp[maxn],P[maxn]; int main(){ cin>>n; for(int i=1;i<=n;i++)scanf("%lld",&a[i]); P[0]=1; for(int i=1;i<=n;i++)P[i]=P[i-1]*2%mod; dp[1]=a[1]*P[n-1]%mod; for(int i=2;i<=n;i++){ dp[i]=((dp[i-1]-a[i-1]*P[n-i]%mod)%mod+mod)%mod; dp[i]=(dp[i]+a[i]*P[n-i]%mod)%mod; } ll ans=0; for(int i=1;i<=n;i++) ans=(ans+dp[i])%mod; cout<<ans<<'\n'; }
转载于:https://www.cnblogs.com/zsben991126/p/11070983.html
