Codeforces1485F

题目链接
参考题解链接
思路
最基本的(dp)状态转移方程都能推。
(dp[i][j]:)到第(i)个数，前缀和为(j)的所有方案数。
考虑第(a_i)的两种选择方式：
1、当(a_i=b_i)时，前缀和为(j)时：
(dp[i][j]=dp[i-1][j-b_i](-inf leq j leq inf)).
2、当前缀和恰为(b_i)时的所有方案数:
(dp[i][b[i]]=dp[i-1][j](-inf leq j leq inf)).

观察第一个式子，可以发现每次相当于把这整个dp左移(b_i)个单位。
对于第二个式子，那么发现(dp[i][b[i]])所记录的就是(i-1)的所有情况，即是记录过的res。
代码中的sum其实就可以当作一个基准标，每次向左移动(b[i])，因此对于每次读入的循环先需要(sum-b[i])。(mp)记录的是前缀和为(b[i])的所有方案数，因为基准标在向左移动，所以此时的前缀相当于(sum+b[i])。(mp[sum+b[i]])就要更新为新的(res)，那么新增加的方案数即是(res-mp[sum+b[i]])。

const int N = 2e5 + 10, M = 1e5 + 10;
const int mod = 1e9 + 7;
int a[N];
map<int, int> mp;
void solve() {
    mp.clear();
    int n;
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    mp[0] = 1;
    int res = 1;
    LL sum = 0;
    for(int i = 1; i <= n; i++) {
        sum -= a[i];
        LL x = res - mp[sum + a[i]];
        mp[sum + a[i]] = res;
        res = (res + x + mod) % mod;
    }
    printf("%lld
", res);
}