【題解】Codeforces 1485F. Copy or Prefix Sum

【題目敘述】https://codeforces.com/contest/1485/problem/F

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

long long t, n, b[200005], pre[200005], tot, p = 1e9+7;
map <long long, long long> dp;

int main(){
    cin >> t;
    while (t--){
        cin >> n;
        cin >> b[1];
        pre[1] = b[1];
        dp.clear();
        dp[0] = 1;
        tot = 1;
        for (int i = 2; i <= n; i++){
            cin >> b[i];
            pre[i] = pre[i-1]+b[i];
            tot -= dp[pre[i]-b[i]];
            tot = (tot+p)%p;
            dp[pre[i]-b[i]] += tot;
            dp[pre[i]-b[i]] %= p;
            tot += dp[pre[i]-b[i]];
            tot %= p;
        }
        cout << tot << "\n";
    }
}
分享本文 Share with friends