自动搬运

查看原文

来自洛谷，原作者为

	君のNOIP。 清新出题人

搬运于2025-08-24 22:24:37，当前版本为作者最后更新于2020-09-19 15:19:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$p_0:$ 讲个笑话，正解分块。

---

数据点 $1\sim 4$： $O(2^nn)$ 暴力枚举子序列即可。

---

数据点 $12$：$k=0$

合法的子序列均只有一个元素，答案显然为 $\sum \limits _{i=1} ^n a_i^2$。

---

数据点 $5\sim 11$： $O(n^2)$ 暴力递推。

先不考虑不合法的子序列，即 $k=n-1$ 的情况，将 $\sum \limits _{i=1} ^ x s_i$ 和 $\prod \limits _{i=1} ^ x s_i$ 分开看。

设 $f_n$ 为考虑前 $n$ 个元素的答案。

显然 $f_n$ 表示的答案中由 $2^n -1$ 个非空子集组成，设第 $i$ 个子集的值为 $w_i \times b_i$

显然 $f_n$ 的形式为 $\sum \limits _{i=1} ^ {2^n-1} w_i \times b_i$ 。

再设 $g_n =\sum \limits _{i=1} ^ {2^n-1} b_i$ 。

那么 $f_{n+1}$ 表示的答案由 $3$ 个部分组成：

• $\{ a_{n+1} \}$ 的值。

• $f_n$ 表示的 $2^n - 1$ 个子集的值。

• $f_n$ 表示的 $2^n - 1$ 个子集分别加上元素 $a_{n+1}$ 的值。

那么我们分别考虑这 $3$ 个部分可以得到：

$\begin{aligned}f_{n+1} & = a_{n+1}^2 + f_n + \sum \limits _{i=1} ^ {2^n-1} (w_i+a_{n+1}) \times (b_i \times a_{n+1}) \\ & = a_{n+1}^2 + f_n + \sum \limits _{i=1} ^ {2^n-1} (w_i \times b_i \times a_{n+1} + b_i \times a_{n+1}^2 ) \\ & = a_{n+1}^2 + f_n + f_n \times a_{n+1} + g_n \times a_{n+1}^2 \\ & = a_{n+1}^2 \times (g_n + 1) + f_n \times ( a_{n+1} + 1 ) \end{aligned}$

关于 $g_n$，根据乘法结合律，同理考虑 $3$ 个部分易得：

$\begin{aligned}g_{n+1} &= a_{n+1} + g_n + g_n \times a_{n+1} \\ & = a_{n+1} \times (g_n+1) + g_n \end{aligned}$

$f_{n+1} = a_{n+1}^2 \times ( g_n + 1) + f_n \times ( 1 + a_{n+1} )$

于是我们就可以 $O(n)$ 同时递推两个式子，答案即为 $f_n$。

而现在我们需要考虑去掉不合法的序列。

改设 $f_{i,j}$ 为 $i \le p_1 \le p_x \le j$ 的所有子序列的值之和， $g_{i,j}$ 同理。

发现由上式的原理可以由 $f_{i,j}$ 推至 $f_{i-1,j}$ 和 $f_{i,j+1}$， $g_{i,j}$ 同理。

根据基本容斥原理，答案为 $\sum \limits _{i=1} ^{n-k} f_{i,i+k} - \sum \limits _{i=2} ^{n-k} f_{i,i+k-1}$。

---

数据点 $15\sim 17$： $O(nlogn)$ 逆元。

根据前文中推出的式子，同理：

$f_{i,j} = f_{i+1,j} \times (a_i + 1 ) + a_i ^ 2 \times g_{i+1,j} $

移项得：

$f_{i+1,j} = ( f_{i,j} - a_i ^ 2 \times g_{i+1,j} ) / ( a_i + 1 )$

同理 $g_{i,j}$ 可推得 $g_{i+1,j}$。

由于 $mod = 10^9+7$， 是质数，我们只需用逆元即可运用类似双指针的方法推得答案。

---

数据点 $18\sim 22$： $O(nlogn)$ 合并区间 $\&$倍增。

我们是否能由 $f_{i,l}$ 和 $f_{l+1,j}$ 合并得 $f_{i,j}$ 呢？

方法与由 $f_{i,j}$ 推至 $f_{i,j+1}$ 是一样的，同理可推得：

$f_{i,j} = f_{i,l} \times (g_{l+1,j} + 1 ) + f_{l+1,j} \times (g_{i,l} + 1 ) $

$g_{i,j} = g_{i,l} + g_{l+1,j} + g_{i,l} \times g_{l+1,j} $

接下来只要利用倍增的思想，预处理出 $f_{i,i+2^j-1},g_{i,i+2^j-1}$ ,再倍增求出 $f_{i,i+k}$ 和 $f_{i+1,i+k}$ 即可。

时空复杂度都是 $O(nlogn)$。

---

数据点 $23\sim 25$：

正解 $O(n)$，但由于这是乐多赛制缺少试错的机会，且作为信心赛题目，良心出题人放了很多略加优化的 $O(nlogn)$ 乱搞做法通过。

• 乱搞一：

仍然倍增，但空间会炸，于是我们类似分块，以 $10$ 为块大小，再倍增记录每块的信息即可。空间上足够了，但是由于常数巨大，经测试，#23 很难卡过去。

• 乱搞二：

据说有方法可以实现膜数非质数逆元，不太了解这里就不讲了，但时间复杂度仍然要 $O(nlogn)$。

• 乱搞三：

区间合并，区间查询，显然可以线段树，时间复杂度 $O(logn)$，空间复杂度 $O(n)$。

注意由于要同时合并 $f_{i,j},g_{i,j}$，求和的时候要是分两个函数求解，则会产生重复递归（和 T1 不加 map 记忆化搜索是一个道理 ），时间复杂度会退化成 $O(n^2)$。

我的方法是直接用 pair<> 作函数类型，如果有其它方法欢迎评论提出。

但由于线段树巨大的常数还是有一定风险的，事实上出题人写的线段树这 $3$ 个点一个都过不去。

• 正解：分块。

大家都知道分块一般是 $n^{1.5}$ 的，但这里不太一样。

因为我们要求的区间长度只有 $k$ 和 $k+1$。

所以我们可以以 $k$ 为块的大小，设 $i$ 所在块左边界为 $l_i$，右边界为 $r_i$。

则我们只需预处理出 $f_{l_i,i},f_{i,r_i}$，则计算答案的时候每次也只要合并两个区间 $f_{i,r_i},f_{l_j,j}$ 即可。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
#define G() Cr = getchar()
#define LL long long
LL Xr, Fr; char Cr;
inline LL rd() {
	Xr = 0, Fr = 1, G();
	while(Cr < '0' || Cr > '9') {if(Cr == '-') Fr = -1; G();}
	while(Cr >= '0' && Cr <= '9') Xr = (Xr<<1) + (Xr<<3) + (Cr&15), G();
	return Xr * Fr;
}
#define MAX_N 1000005
LL n, k, mod;
LL va[MAX_N], f[MAX_N][3], b[MAX_N][3], l[MAX_N], r[MAX_N], ans, s; // 0 -> from left ; 1 -> from right

LL work( LL L, LL R ) {
	if( L == R ) return va[L] * va[L] % mod;
	if( l[L] == l[R] ) return f[R][0];
	LL x, y, A, B;
	x = f[L][1], y = f[R][0];
	A = b[L][1], B = b[R][0];
	return ( x + y + A * y % mod + B * x % mod ) % mod;
}

int main() {
	n = rd(), k = rd(), mod = rd();
	for( int i = 1; i <= n; i++ ) va[i] = rd();
	if(!k) {
		for( int i = 1; i <= n; i++ ) ans = ( ans + va[i] * va[i] ) % mod;
		cout << ans;
		return 0;
	}
	for( int i = 1; i <= n; i++ ) l[i] = ( i - 1 ) / k * k + 1, r[i] = ( ( i - 1 ) / k + 1 ) * k;
	for( int i = 1; i <= n; i++ ) {
		if( i == l[i] ) b[i][0] = va[i], f[i][0] = va[i] * va[i] % mod;
		else {
			f[i][0] = (va[i] * va[i] % mod * ( 1 + b[i-1][0] ) % mod + f[i-1][0] * ( 1 + va[i] ) % mod ) % mod;
			b[i][0] = ( b[i-1][0] * ( 1 + va[i] ) + va[i] ) % mod;
		}
	}
	for( int i = n; i >= 1; i-- ) {
		if( i == r[i] ) b[i][1] = va[i], f[i][1] = va[i] * va[i] % mod;
		else {
			f[i][1] = (va[i] * va[i] % mod * ( 1 + b[i+1][1] ) % mod + f[i+1][1] * ( 1 + va[i] ) % mod ) % mod;
			b[i][1] = ( b[i+1][1] * ( 1 + va[i] ) + va[i] ) % mod;
		}
	}
	for( int i = k + 1; i < n; i++ )
		ans = ( ans + work(i-k,i) - work(i-k+1,i) + mod ) % mod;
	ans = ( ans + work(n-k,n) ) % mod;
	cout << ans;
}