【牛客网】一个有意思的前缀和题目
程序员文章站
2022-03-12 16:56:21
...
这个挺有意思的
想法:
对于 n==5 要是暴力求解的话,会有一种这样的情况
/*
n == 5 时, 暴力求解的表
a1 a2 a3 a4 a5
1 1 1 1 1 w5
1 1 1 1 w4
1 1 1 1 w4
1 1 1 w3
1 1 1 w3
1 1 1 w3
1 1 w2
1 1 w2
1 1 w2
1 1 w2
1 1 1 1 1 w1
(对于区间长度为1的就放在一行了)
*/
将表的横向的w合并
/*
5 8 9 8 5
a1 a2 a3 a4 a5
1 1 1 1 1 w1
1 2 2 2 1 w2
1 2 3 2 1 w3
1 2 2 2 1 w4
1 1 1 1 1 w5
将矩阵取名为 cnt
我们要求的答案就是 ai*wj*cnt[i][j];
*/
怎么快速求这个的答案呢
/*
对于 (a1+a2+a3+a4+a5)*(w1+w2+w3+w4+w5) 得到的矩阵就是
a1 a2 a3 a4 a5
1 1 1 1 1 w1
1 1 1 1 1 w2
1 1 1 1 1 w3
1 1 1 1 1 w4
1 1 1 1 1 w5
对于 (a2+a3+a4)*(w2+w3+w4) 得到的矩阵就是
a1 a2 a3 a4 a5
0 0 0 0 0 w1
0 1 1 1 0 w2
0 1 1 1 0 w3
0 1 1 1 0 w4
0 0 0 0 0 w5
对于 a3*w3 得到的矩阵就是
...............
*/
代码:
#include <bits/stdc++.h>
const int maxn = 3e5 + 50;
const long long mod = 1e9 + 7;
using namespace std;
typedef long long ll;
ll a[maxn], w[maxn];
inline ll read()
{ //读入及输出优化
ll x = 0, f = 1;
char ch = getchar();
while (ch > '9' || ch < '0')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x *= 10;
x += (ch - '0');
ch = getchar();
}
return x * f;
}
int main()
{
int n;
n = read();
for (int i = 1; i<=n; i++){
a[i] = read();
a[i] = (a[i] + a[i - 1]) % mod;
}
for (int i = 1; i <= n; i++){
w[i] = read();
w[i] = (w[i] + w[i - 1]) % mod;
}
ll ans = 0;
for (int i = 1; i <= (n + 1) / 2; i++){
ll t = (a[n - i + 1] - a[i - 1]) * (w[n - i + 1] - w[i - 1]);
ans = (ans + t%mod) % mod;
}
printf("%lld\n", ans);
// getchar();
// getchar();
return 0;
}
烦操,要是不加输入挂还会超时,取模太多,输入太大?????又开心的水了一天的题,✌