QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#589518#6810. Array ConcatenationSunlight9#WA 9ms6460kbC++201.6kb2024-09-25 18:14:352024-09-25 18:14:36

Judging History

你现在查看的是最新测评结果

  • [2024-09-25 18:14:36]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:6460kb
  • [2024-09-25 18:14:35]
  • 提交

answer

#include <bits/stdc++.h>

//using namespace std;

using ll = long long;
using LL = unsigned long long;
using i128 = __int128;
constexpr int N = 1E5 + 10;
constexpr int mod = 1E9 + 7;
using std::cin;
using std::cout;
using std::vector;
using std::cerr;
using std::pair;


LL p[N] = {};

int init = []() {
    p[0] = 1;
    for (int i = 1; i < N; i++) {
        p[i] = (p[i - 1] + p[i - 1]) % mod;
    }
    return 0;
}();

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n, m;
    cin >> n >> m;

    auto norm = [&](LL x) {
        if (x < 0) x += mod;
        if (x >= mod) x-= mod;
        return x;
    };

    LL sum = 0;
    auto get = [&](vector<int> &a) {
        LL s = 0, now = 0;
        for (int i = 1; i <= n; i++) {
            now += a[i];
            s += now;
        }
        vector<LL> f(m + 1);
        f[0] = s % mod;
        for (int i = 1; i <= m; i++) {
            f[i] = norm(norm(f[i - 1] + f[i - 1]) + sum * p[i - 1] % mod * p[i - 1] % mod * n % mod);
        }
        return pair(s, f);
    };

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    auto [s1, f] = get(a);
//    for (int i = 0; i <= m; i++) {
//        cout << f[i] << " \n"[i == m];
//    }
    reverse(a.begin() + 1, a.end());
    auto [s2, g] = get(a);
//    for (int i = 0; i <= m; i++) {
//        cout << g[i] << " \n"[i == m];
//    }
    if (s1 > s2) {
        cout << f[m] << "\n";
    } else {
        cout << norm(norm(f[m - 1] + g[m - 1]) + sum * p[m - 1] % mod * n % mod * p[m - 1] % mod);
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4564kb

input:

2 1
1 2

output:

15

result:

ok single line: '15'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4628kb

input:

5 10
26463 39326 86411 75307 85926

output:

806275469

result:

ok single line: '806275469'

Test #3:

score: 0
Accepted
time: 1ms
memory: 4532kb

input:

3 10000
329770536 859936159 696111818

output:

325223749

result:

ok single line: '325223749'

Test #4:

score: 0
Accepted
time: 0ms
memory: 6140kb

input:

10 100000
910385778 832405357 79882277 740539785 58009121 361679935 208356273 191444931 327043571 40502864

output:

551220212

result:

ok single line: '551220212'

Test #5:

score: -100
Wrong Answer
time: 9ms
memory: 6460kb

input:

99998 99999
424541359 970848132 124944765 190568793 218987145 439687684 674898132 26756266 495705287 999481800 123311748 808192729 480063991 282558300 432664601 480692564 771223766 592954167 648647039 80490877 501738111 3075724 426165921 557518328 209501102 786985447 129062653 705971029 763019010 16...

output:

855779246

result:

wrong answer 1st lines differ - expected: '371554090', found: '855779246'