欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【牛客网】一个有意思的前缀和题目

程序员文章站 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;
}

烦操,要是不加输入挂还会超时,取模太多,输入太大?????
又开心的水了一天的题,✌