Codeforces 1485F-Copy or Prefix Sum-DP

传送门

题意

给你一个n个数的序列 b b b

求有多少个序列 a a a满足对于每个 i ( 1 ≤ i ≤ n ) i(1\leq i\leq n) i(1≤i≤n)，至少满足以下两个条件之一：

1. b i = a i b_i=a_i bi​=ai​

2. b i = ∑ j = 1 i a j b_i=\sum_{j=1}^ia_j bi​=∑j=1i​aj​

n ≤ 2 ∗ 1 0 5 n\leq 2*10^5 n≤2∗105

Solution

最朴素的DP：

d p i , j dp_{i,j} dpi,j​表示前i个数和为j的情况下，有多少个不同的方案，转移分成上面那两个条件进行转移：

d p i , j + b i = d p i − 1 , j dp_{i,j+b_i}=dp_{i-1,j} dpi,j+bi​​=dpi−1,j​

d p i , b i = ∑ k = − i n f i n f d p i − 1 , k dp_{i,b_i}=\sum_{k=-inf}^{inf}dp_{i-1,k} dpi,bi​​=∑k=−infinf​dpi−1,k​

注意当j为0的时候，两个转移会重复，只能进行第二个转移

结合map,可以做到 O ( n 2 log ⁡ n ) O(n^2\log n) O(n2logn)的复杂度

我们注意到第一个转移相当于平移DP数组，第二个转移相当于在某一特定位置加上dp数组的总和，因此我们可以用一个变量 t o t tot tot记录数组整体偏移量，再用一个变量 s u m sum sum记录当前DP数组的和，就可以方便地转移了。

总复杂度: O ( n log ⁡ n ) O(n\log n) O(nlogn)

代码：

#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
int n,T;
int a[200010];
const int mod=1e9+7;
map<long long,int> dp;
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		long long tot=0;
		int sum=1;
		dp[0]=1;
		for (int i=1;i<=n;i++)
		{
			int add;
			add=(sum-dp[-tot]+mod)%mod;
			dp[-tot]+=add;sum+=add;
			dp[-tot]%=mod;if (sum>=mod) sum-=mod;
			tot+=a[i];
		//	cout<<i<<" "<<sum<<endl;
		}
		printf("%d\n",sum);
		dp.clear();
	}
}