题解 AT2326 【数列と計算】

Shawk · 2020-07-09 21:10:17 · 题解

一个式子里既有加号又有乘号，不好处理，可以想最后一个加号的位置，有n-1种情况：
定义f[i]为前i个数据题意求出的和，有：

f_i \doteq \sum_{j=1}^{i-1}(f_j+\prod_{k=j+1}^{i}a_k\times 2^{j-1})+\prod_{k=1}^{i}a_k

将第一项拆开，得到

f_i \doteq \sum_{j=1}^{i-1}f_j+\sum_{j=1}^{i-1}(\prod_{k=j+1}^{i}a_k\times 2^{j-1})+\prod_{k=1}^{i}a_k

然后就根据这个式子求就可以了

f[i] = s[i-1] + sp[i] + p[i];//一一对应

代码


#include <cstdio>
#define int long long
using namespace std;
const int N = 1e5+5, M = 1e9+7;
int n, a[N], f[N], s[N], sp[N], p[N];
int qpow(int a, int x) {
    int ans = 1;
    while (x) {
            if (x & 1) ans = ans * a % M;
            a = a * a % M;
            x >>= 1;
    }
    return ans;
}
signed main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i)
            scanf("%lld", &a[i]);
    f[1] = s[1] = p[1] = a[1] % M;
    for (int i = 2; i <= n; ++i) {
            sp[i] = (sp[i-1] * a[i] % M + a[i] * qpow(2, i-2) % M) % M;
            p[i] = p[i-1] * a[i] % M;
            f[i] = (s[i-1] + sp[i] + p[i]) % M;
            s[i] = (s[i-1] + f[i]) % M;
    }
    printf("%lld\n", f[n]);
    return 0;
}