CF1009E [Intercity Travelling]

Intercity Travelling]"/>

CF1009E [Intercity Travelling]

这道题先考虑一种暴力n方做法

设\(f_i\)表示到\(i\)点所有情况的困难度之和(\(f_0=0\)),\(pre_i=\sum_{j=1}^{i} a_j\)

考虑从点\(j\)中途不经过休息站到达\(i\),可以得到\[f_i=pre_i+\ \sum_{j=1}^{i-1} f_j+2^{j-1}pre_{i-j}\]

(要乘\(2^{j-1}\)是因为到第\(j\)个点有那么多方案)

这个很容易就能优化到\(O(n)\)

记\(g_i=\sum_{j=1}^{i} f_j,h_i=pre_i+\sum_{j=1}^{i-1} 2^{j-1}pre_{i-j}=\sum_{j=1}^{i}2^{i-j}a_j=2h_{i-1}+a_i\)

所以\[f_i=g_{i-1}+h_i\]

直接\(O(n)\)救星了,也不要多开数组

#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define db doubleusing namespace std;
const int mod=998244353,N=1000000+10;
il LL rd()
{re LL x=0,w=1;re char ch;while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*w;
}
LL n,a[N],an,ss,bb; //乱定变量名(逃int main()
{n=rd();for(int i=1;i<=n;i++) a[i]=rd();for(int i=1;i<=n;i++){bb=((bb<<1)%mod+a[i])%mod;an=(ss+bb)%mod;ss=(ss+an)%mod;}printf("%lld\n",an);return 0;
}

转载于:.html