CF1485F Copy or Prefix Sum 题解

思路

考虑 \(a_i\) 要么是 \(b_i\) 要么是 \(b_i - s\)。

考虑 \(s\) 代表着什么。

它是 \(a\) 的前缀和。

那么必然是往前一段 \(b\) 的和。

因为每个 \(b\) 代表着要么是这一位的 \(a\) 或者前面所有的 \(a\)。

考虑设 \(f_i\) 为这个位置填 \(b_i\) 的方案数。

\(g_i\) 为这个位置填与 \(b_i\) 不同的 \(b_i - s\) 的方案数。

那么有：

下面这个式子可以直接哈希表优化，实现使用的 \(\text{map}\)。

Code

/**
 * @file 1485F.cpp
 * @author mfeitveer
 * @date 2023-11-10
 * 
 * @copyright Copyright (c) 2023
 * 
 */
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
#define dbg cerr << "Line " << __LINE__ << ": "
#define EVAL(x) #x " = " << (x)

typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> PII;

bool ed;

const int N = 1000010;
const int mod = 1e9 + 7;

int n, m;
i64 all, g[N], f[N], a[N], sum[N];

inline void mo(i64 &x)
	{ x = (x % mod + mod) % mod; }
inline void solve()
{
	cin >> n;
	fro(i, 1, n) cin >> a[i], sum[i] = sum[i - 1] + a[i];
	map<i64, i64> mp; f[1] = all = mp[0] = 1;
	fro(i, 2, n)
	{
		i64 x = all - mp[sum[i - 1]];
		g[i] = x, f[i] = g[i - 1] + f[i - 1];
		mo(g[i]), mo(f[i]);
		all += g[i], mp[sum[i - 1]] += g[i];
		mo(all), mo(mp[sum[i - 1]]);
	}
	cout << (g[n] + f[n]) % mod << "\n";
}

bool st;

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	double Mib = fabs((&ed-&st)/1048576.), Lim = 1024;
	assert(Mib<=Lim), cerr << " Memory: " << Mib << "\n";
	int t; cin >> t;
	while(t--) solve();
	return 0;
}