CF1485F

lsj2009 · 2023-11-07 02:00:02 · 题解

Solution

妙妙题。

朴素地，我们考虑设 f_{i,j} 为考虑前 i 个数且 \sum\limits_{k=1}^i a_k=j 的方案总数，但是 j 过大肯定寄飞。但是考虑到转移只有两种：

1. 当取 a_i=b_i 时，f_{i,j}\gets f_{i-1,j-b_i}。
2. 当取 \sum\limits_{k=1}^i a_k=b_i 时，f_{i,b_i}\gets \sum\limits_x f_{i-1,x}。

第一种转移其实相当于全局位移，我们不妨考虑维护一个 \Delta=\sum\limits_{k=1}^i b_k；对于第二种操作，相当于全局求和，我们维护一个 sum。当进行第二种操作时，由于是全局求和，所以必然也包含原来的 f_{\Delta}，所以需要减去，否则会重复计算。即令 f'_{\Delta}\gets sum,sum'\gets (sum-f_{\Delta})+f'_{\Delta}。

然后就做完了。由于数组很大，所以需要开 map 保存，复杂度 \Theta(n\log{n})。

Code

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int MOD=1e9+7;
map<int,int> f;
signed main() {
    int T;
    scanf("%lld",&T);
    while(T--) {
        f.clear();
        int n;
        scanf("%lld",&n);
        int res=0,ans=f[0]=1;
        while(n--) {
            int x;
            scanf("%lld",&x);
            int val=ans-f[res];
            f[res]=ans;
            ans=((ans+val)%MOD+MOD)%MOD;
            res-=x;
        }
        printf("%lld\n",ans);
    }
    return 0;
}