CF1485F Copy or Prefix Sum

题目描述

给定一个 b 数组,一个 a 是合法的指对于每一个 i 都能满足
b_i=a_i

b_i=\sum\limits_{j=1}^{i}a_j
问合法的 a 有多少个。

Solution

如果没有重复,那么会有 2^{n-1}

\sum\limits_{j=1}^{i-1}a_j=0 时,对于第 i 来说,两种操作是等价的,所以 2^{n-1} 种方案中肯定有许多重复的。

想到 dp ,于是考虑设计状态,

设计 dp(i,j) 表示,对于前 i 个元素来说,a 的前缀和为 j 的有多少种

那么转移方程就是:
j\neq b_i\qquad dp[i][j]= dp[i-1][j-b[i]] \qquad j\in Z

j=b_i\qquad dp[i][b[i]]=dp[i-1][k] \qquad k \in Z

j=b_i 中其实包含了第一种的转移)

这个复杂度是 O(n^2logn) 的(因为用 map 存)

考虑第一种操作,其实就是将数组整体平移。

而第二种操作,就是存一下当前所有数组的值,是一个单点修改操作。

所以我们维护一下整体值,再维护一个偏移量即可,具体可以看 这里

也可以看 CF 的官方题解WNLU__C_M_RSF8DN_RR11_N.png,讲得非常清晰

#include<bits/stdc++.h>
#define LL long long
LL mod = 1e9+7;
const int N = 2*1e5+10;
int a[N],n,t;
std::map<LL,LL> dp;
int main(){
    scanf("%d",&t);
    while(t--){
        dp.clear();
        scanf("%d",&n);
        for(int i=1; i<=n; ++i)
            scanf("%d",&a[i]);
        LL sum = 0 , derta = 0;
        dp[0] = 1 ; sum = 1 ;
        for(int i=1; i<=n; ++i){
            LL tmp = dp[derta];
            dp[derta] = sum ; 
            sum = ( sum * 2 - tmp + mod ) % mod;
            derta += a[i];
        }
        printf("%lld\n",sum);
    }
    return 0;
} 
分类: DP

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注