1485F. Copy or Prefix Sum(DP+懒惰标记)

给出一个数组\(b\)

\(b_i\)可以等于\(a_i\),也可以等于\(\sum_{j=1}^ia_j\)

询问有多少个数组\(a\)。

对每个位置\(i\),你可以选择\(a_i=b_i\)或\(a_i=b_i-\sum_{k=1}^{i-1}a_k\)。

如果\(\sum_{k=1}^{i-1}a_k=0\),那么这两种选择构成的数组是一样的,对答案的贡献是1。

一种\(O(n^2logn)\)的做法:

定义\(f(i,j)\)是当前在第\(i\)位,前缀和是\(j\)的情况有多少种。

状态转移方程:

如果你选择\(b_i=a_i\),同时\(j \neq 0\):

\(f(i+1,j+b_i)=f(i,j)\)

如果你选择\(b_i=\sum_{k=1}^ia_k\):

\(f(i+1,b_i)=f(i,j)\)

用\(Map\)实现状态转移方程可以把时间复杂度控制在\(O(n^2logn)\)。

观察状态转移方程,就是把当前位置的所有\(j \neq 0\)的\(f(i,j)\)变成\(f(i+1,j+b_i)\),同时把所有\(f(i,j)\)加给\(f(i+1,b_i)\)。

第二步就是当前的情况数,第一步就是当前的情况数减去\(j=0\)的情况数。

合并就是:下一步的情况数=当前的情况数*2-\(j=0\)的情况数。

怎么快速计算\(j=0\)的情况数:

考虑到每一步,所有状态统一加\(b_i\),那么第二步可以转化为把所有的\(f(i,j)\)加给\(f(i+1,0)\),然后把两步的所有情况都变成\(f(i+1,j+b_i)\)。

维护一个懒惰标记,标记当前一共加了多少(即\(b\)的前缀和)。可以直接用\(lazy\)表示。

然后转移的时候,\(f(lazy)\)就表示当前\(j=0\)的情况,每次转移把\(lazy\)减\(b_i\)即可。

时间复杂度\(O(nlogn)\)

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
const int mod=1e9+7;
int b[maxn],n,t;
map<long long,long long> f;
int main () {
	scanf("%d",&t);
	while (t--) {
		scanf("%d",&n);
		for (int i=1;i<=n;i++) scanf("%d",b+i);
		f.clear();
		long long lazy=0;
		long long ans=1;
		f[0]=1; 
		for (int i=1;i<=n;i++) {
			long long tt=ans;
			ans=(ans*2-f[lazy]+mod)%mod;
			f[lazy]=tt%mod;
			lazy-=b[i];
		}
		ans%=mod;
		printf("%lld\n",ans);
	}
}
上一篇:nginx教程一,编译生成nginx


下一篇:Codeforces 1485F Copy or Prefix Sum