CF1485F

GsjzTle · 2021-03-08 18:03:55 · 题解

题目链接

点我跳转

题目大意

给定一个长度为 N 的序列 bi

问有多少个长度为 N 的序列 a 使得

• b[i] = a[i]

或

• b[i] = ∑a[j] , j∈[1,i]

解题思路

定义 dp[i][j] 表示前 i 项的前缀和为 j 的序列 a 的个数，其中 dp[0][0] = 1

( 因为前缀和很大，所以需要用 map 来操作 )

那么：

1. 当 b[i] = a[i] 时 , dp[i][j] = dp[i - 1][j - b[i]]

2. 当 b[i] = ∑a[j] , j∈[1,i] 时 , dp[i][b[i]] = ∑dp[i - 1][j],j∈[-inf,inf]

对于第一种转移相当于把整个数组的值向右平移 b[i]

对于第二种转移需要注意当 sum[i-1] = 0 时，b[i] 既等于 a[i] 又等于 ∑a[j] , j∈[1,i]

相当于多转移了一次 dp[i - 1][0] ，所以需要减去 dp[i - 1][0]

最后的答案 ans = ∑dp[n][j],j∈[-inf,inf] ，复杂度为 N^2logN ( log 的复杂度源于 map )

考虑优化：

定义 sum[i] 表示长度为 i 且满足题目条件的序列 a 的个数

对于第一种转移，只是把数值向右平移，并不会导致答案的个数增加，所以 sum[i] = sum[i - 1]

对于第二种转移，dp[i][b[i]] += sum[i - 1] , 同时减去 dp[i - 1][0] ，相当于 sum[i] += sum[i - 1] , sum[i] -= dp[i - 1][0]

于是我们可以定义 py 表示平移的长度，起初 py = 0，每计算完 sum[i] 后 , 令 py += b[i]

那么 dp[i - 1][j] 则可以用 dp[j - py] 表示

而 dp[i][j] 则可以用 dp[j - py - b[i]] 表示

于是可得 sum[i] += sum[i - 1] - dp[0 - py] , dp[b[i] - py - b[i]] += sum[i - ] - dp[0 - py]

最后的答案 ans = sum[n] , 复杂度为 NlogN

AC_Code

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N = 3e5 + 10 , mod = 1e9 + 7;

map<int , int>dp;

int b[N];

signed main()
{
    int T = 1;

    cin >> T;

    while(T --)
    {
        dp.clear();

        int n , sum = 1 , py = 0;

        cin >> n;

        for(int i = 1 ; i <= n ; i ++) cin >> b[i]; 

        dp[0] = 1;

        for(int i = 1 ; i <= n ; i ++)
        {
            int add = (sum - dp[0 - py] + mod) % mod;

            sum = (sum + add) % mod , py += b[i];

            dp[b[i] - py] = (dp[b[i] - py] + add) % mod;
        }

        cout << sum << '\n';
    }

    return 0;
}