洛谷 P5686 [CSP-SJX2019]和积和

思路

应用多个前缀和推出式子即可

\(30pts\)：

首先如果暴力算的话很简单，直接套三层循环就好了(真的是三层！！最后两个\(sigma\)一起算就好了)

\[\sum_{l = 1}^{n}\sum_{r = l}^{n}\sum_{i = l}^{r}a[i]\sum_{i = l}^{r}b[i]
\]

\(70pts\)：

其实不用这么麻烦，我们发现最后两个\(sigma\)可以用前缀和\(O(1)\)算出来，这样就可以\(70\)分了（见代码\(sub1\)）

\(100pts\)：

考虑再拆一层循环（这里用\(SA\)和\(SB\)数组表示70分钟\(a\)数组和\(b\)数组的前缀和）

我觉得你可以自己展开式子（毕竟不能太懒嘛）

然后就会得到这样一个式子

\[\sum_{l = 1}^{n}(SA[l] * SB[l] + SA[l + 1] * SB[l + 1] + ...+SA[n] * SB[n]) - (SA[l] + SA[l + 1] + ... + SA[n]) * SB[l - 1] - (SB[l] + SB[l + 1] + ... + SB[n]) * SA[l - 1] + (n - l + 1) * SA[l - 1] * SB[l - 1]
\]

我们发现这些东西基本都可以用前缀和再求一遍，所以我们要求一下\((SA[l] * SB[l] + SA[l + 1] * SB[l + 1] + ...+SA[n] * SB[n])\)的前缀和（代码中为\(woc\)数组），求一下\(SA\)数组的前缀和（代码中为\(qza\)数组），求一下\(SB\)数组的前缀和（代码中为\(qzb\)数组），然后就可以\(O(n)\)做这道题啦

下面上代码

代码

#include <cstdio>

#include <cstring>

#include <iostream>

#define int long long

using namespace std;

const int A = 5e5 + 11;

const int mod = 1e9 + 7;

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for( ; isdigit(c); c = getchar()) x = x * 10 + c - 48;

	return x * f;

}

int n, a[A], b[A], ans = 0, SA[A], SB[A], qza[A], qzb[A];

int woc[A];

void sub1() {

	for(int l = 1; l <= n; l++) {

		for(int r = l; r <= n; r++) {

			ans = (ans + ((SA[r] - SA[l - 1]) % mod + mod) % mod * ((SB[r] - SB[l - 1]) % mod + mod)) % mod;

		}

	}

	cout << ans << '\n';

	return;

}

signed main() {

	n = read();

	for(int i = 1; i <= n; i++) a[i] = read(), SA[i] = (SA[i - 1] + a[i]) % mod;

	for(int i = 1; i <= n; i++) b[i] = read(), SB[i] = (SB[i - 1] + b[i]) % mod;

	if(n <= 3000) return sub1(), 0;

	for(int i = 1; i <= n; i++) woc[i] = (woc[i - 1] + SA[i] * SB[i]) % mod;

	for(int i = 1; i <= n; i++) qza[i] = (qza[i - 1] + SA[i]) % mod;

	for(int i = 1; i <= n; i++) qzb[i] = (qzb[i - 1] + SB[i]) % mod;

	for(int i = 1; i <= n; i++) {

		int fuck1 = ((woc[n] - woc[i - 1]) % mod + mod) % mod;

		int fuck2 = ((qza[n] - qza[i - 1]) % mod + mod) % mod * SB[i - 1] % mod;

		int fuck3 = ((qzb[n] - qzb[i - 1]) % mod + mod) % mod * SA[i - 1] % mod;

		int fuck4 = (((n - i + 1) % mod * SA[i - 1] % mod * SB[i - 1]) % mod + mod) % mod;

		int now = fuck1 - fuck2 - fuck3 + fuck4;

		ans = ((ans + now % mod) % mod + mod) % mod;

	}

	cout << ans << '\n';

	return 0;

}

巴特西

洛谷 P5686 [CSP-SJX2019]和积和

洛谷 P5686 [CSP-SJX2019]和积和

思路

代码

最新文章

热门文章