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 << '
';
	}
	
	return 0;
}