CF1485F Cpoy or Prefix Sum 超高质量题解

· · 题解

F - Copy or Prefix Sum

Problem F Cpoy or Prefix Sum

Translation

给定一个 b 数组，一个 a 是合法的指对于每一个 i 都有 b_i=a_i b_i=\sum\limits_{j=1}^{i}a_j 。问合法的 a 有多少个。

1\le t\le 10^4,1\le \sum n\le 2\times 10^5,-10^9\le b_i\le 10^9

Word

Solution

看着这个式子，很明显就是一个DP。

因为题目中 a 可以等于 b_i=\sum\limits_{j=1}^{i}a_j，所以DP考虑维护前缀和。f[i][j] 表示前 i 个数中，前缀和为 j 的方案数。初始化经典 f[0][0]=1 ，最终的答案很明显就是 \sum\limits_{j=min}^{max}f[n][j]。 有了边界，答案，开考虑转移方程。

因为有两种情况，所以分类讨论。

当 a[i] 等于 b[i] 时：

对于 j\in[min,max] 很明显

当 a[i] 等于 b_i=\sum\limits_{j=1}^{i}a_j 时，我们计算前缀和 sum[i]，即此时 a[i]=b[i]-sum[i-1]：

不过由于数据过大，我们不能直接开数组，但是数据量小，所以我们可以使用 map 来代替数组，进行转移。

但是我们这样暴力循环递推，并且因为使用到了 map ，所以总的时间复杂度为O(n^2logn)，而 1\le n\le 2\times 10^5，所以考虑如何优化。

我们发现实际上第一个转移方程就是所有的元素全部向右移动 b[i] ，所以对于第一种转移，我们只需要记录一下最终向右移动了多少，然后每次 O(1) 转移。

对于第二个转移方程，实际意义就是 f[i][b[i]] 等于前面的所有元素之和，设原来的全局之和（也就是答案）应该是 ans， f[i][b[i]]=ans，原来的 f[i][b[i]] 没了，也就是新的全局和变成了 ans=ans+ans-f[i][b[i]]。

最后因为 -10^9\le b_i\le 10^9，所以有可能答案为负数，所以最后 mod 的时候注意加上 mod 消掉负数。

Code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef int itn;
const int N = 5e5 + 7, M = 1e6 + 7, mod = 1e9 + 7;
const int INF = 1e9 + 7;

int n, m, t, k, q;
ll x, y;
map<ll, ll>mp;
ll b[N];

void solve()
{
    ll deviation = 0, ans = 0;
    scanf("%d", &n);
    mp.clear();

    mp[0] = 1;
    ans = 1;
    for(int i = 1; i <= n; ++ i) {
        scanf("%lld", &b[i]);
    }
    for(int i = 1; i <= n; ++ i) {
        deviation -= b[i];
        ll change = ans - mp[b[i] + deviation];
        mp[b[i] + deviation] = ans;
        ans = ans + change % mod;
    }
    printf("%lld\n", (ans % mod + mod) % mod);
    return ;
}

int main()
{
    scanf("%d", &t);
    while(t -- ) {
        solve();
    }
}