[CF1485F] Copy or Prefix Sum

[CF1485F] Copy or Prefix Sum - dp

Description

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

Solution

设 (f[i][j]) 表示前 i 个数，和为 j 的方案数

如果 ai != j，那么 (i,j) 只能来自 (i-1,j-ai)

否则，(i,j) 可以来源于 (i-1,?)

第一类转移是整体的偏移，第二类转移是单点的赋值

所以我们考虑去维护一个整体的偏移量 offset，表示下标已经左移了多少位

每次我们把和赋值给 ai 位置（下标需要加上偏移量）

然后去更新和

发现，除了原来的 0 位置其它每个值都贡献了两次（移动后、作为和）

因此我们将原来的和翻倍，减去原先 0 位置的值即可

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

#define int long long

const int mod = 1e9 + 7;

void solve()
{
    int n;
    cin >> n;

    map<int, int> f;
    f[0] = 1;

    int offset = 0;
    int sum = 1;

    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        int origin_sum = sum;
        sum *= 2;
        sum -= f[-offset];
        sum %= mod;
        sum += mod;
        sum %= mod;
        f[-offset] = origin_sum;
        offset += a[i];
    }

    cout << sum << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}