Codeforces 1485F Copy or Prefix Sum

题目链接

点我跳转

题目大意

> 给定一个长度为 \(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;
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。