算法
(主客転倒) $O(n)$
只需计算每个数对答案的贡献即可。
当 A = [1, 2, 3, 4, 5, 6]
时,我们有
1 + 2 + 3 + 4 + 5 + 6 = 21
1 - 2 + 3 + 4 + 5 + 6 = 17
1 + 2 - 3 + 4 + 5 + 6 = 15
1 + 2 + 3 - 4 + 5 + 6 = 13
1 + 2 + 3 + 4 - 5 + 6 = 11
1 + 2 + 3 + 4 + 5 - 6 = 9
1 - 2 + 3 - 4 + 5 + 6 = 9
1 - 2 + 3 + 4 - 5 + 6 = 7
1 - 2 + 3 + 4 + 5 - 6 = 5
1 + 2 - 3 + 4 - 5 + 6 = 5
1 + 2 - 3 + 4 + 5 - 6 = 3
1 + 2 + 3 - 4 + 5 - 6 = 1
1 - 2 + 3 - 4 + 5 - 6 = -3
从 $0 \sim 7$ 项的斐波那契数分别是 1 1 2 3 5 8 13 21
第 $0$ 项的系数是 $13$,即 $\rm fib[6]$
第 $1$ 项的系数是 $8 - 5$,即 $\rm fib[1] * fib[5] - fib[0] * fib[4]$
对于其他项也有第 $1$ 项的规律,即 $\rm fib[i] * fib[n - i] - fib[i - 1] * fib[n - i - 1]$。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
// Mod int
const int mod = 1000000007;
struct mint {
uint x;
mint(): x(0) {}
mint(ll x):x((x%mod+mod)%mod) {}
mint operator-() const { return mint(0) - *this;}
mint operator~() const { return mint(1) / *this;}
mint& operator+=(const mint& a) { if((x+=a.x)>=mod) x-=mod; return *this;}
mint& operator-=(const mint& a) { if((x+=mod-a.x)>=mod) x-=mod; return *this;}
mint& operator*=(const mint& a) { x=(ull)x*a.x%mod; return *this;}
mint& operator/=(const mint& a) { x=(ull)x*a.pow(mod-2).x%mod; return *this;}
mint operator+(const mint& a) const { return mint(*this) += a;}
mint operator-(const mint& a) const { return mint(*this) -= a;}
mint operator*(const mint& a) const { return mint(*this) *= a;}
mint operator/(const mint& a) const { return mint(*this) /= a;}
mint pow(ll t) const {
if(!t) return 1;
mint res = pow(t/2);
res *= res;
return (t&1)?res*x:res;
}
bool operator<(const mint& a) const { return x < a.x;}
bool operator==(const mint& a) const { return x == a.x;}
bool operator!=(const mint& a) const { return x != a.x;}
};
mint ex(mint x, ll t) { return x.pow(t);}
istream& operator>>(istream&i,mint&a) {i>>a.x;return i;}
//*
ostream& operator<<(ostream&o,const mint&a) {o<<a.x;return o;}
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<mint> fib(n + 2);
fib[0] = fib[1] = 1;
for (int i = 2; i <= n + 1; ++i)
fib[i] = fib[i - 1] + fib[i - 2];
mint ans = fib[n] * a[0];
for (int i = 1; i < n; ++i) {
mint coeff = fib[i] * fib[n - i] - fib[i - 1] * fib[n - i - 1];
ans += coeff * a[i];
}
cout << ans << '\n';
return 0;
}