题解 CF1009E 【Intercity Travelling】

2018-08-15 20:41:34


竟然是当前最优解?兴奋(逃)


打表好啊(逃)

可以知道总共只有 $2^{n-1}$ 种情况。

那么所求就是所有情况的和。

我们分析一下样例二:

1 ---- 1

1 3 ---- 6
1 1

1 3 3 ---- 20
1 1 3
1 3 1
1 1 1

1 3 3 7 ---- 60
1 1 3 3
1 3 1 3
1 1 1 3
1 3 3 1
1 1 3 1
1 3 1 1
1 1 1 1

//----后的数为这一个矩阵的和。

仔细一瞧,好像发现了什么不得了的事情

可以发现,矩阵 $i$ 的左边 $i-1$ 列等于把矩阵 $i-1$ 复制了一遍,右上角为 $a[i]$ ,剩下的部分等于前一个矩阵剩下的部分再加上 $a[i-1]$ 。

给张图感受下:

pic

(画的丑不要在意)


那么设红色部分的和为 $f[i]$ ,右下角那块黑色为 $g[i]$ ,输入的数组为 $a[i]$ ,则有:

$$f[i]=f[i-1]\times 2+g[i-1]\times 2+a[i-1]+a[i]$$

$$g[i]=g[i-1]\times 2+a[i-1]$$


然后这个数组并不需要保存,所以可以把空间降至 $0.02MB$ (实测)


#include <bits/stdc++.h>
#define re register
using namespace std;

const int MOD=998244353;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int main() {
    re int n=read(),f=0,g=0,a=0,last_a=0;
    for (re int i=1;i<=n;i++) {
        last_a=a,a=read();
        f=((f<<1)%MOD+a+(g<<1)%MOD+last_a)%MOD;
        g=((g<<1)+last_a)%MOD;
    }
    cout<<f;
    return 0;
}