QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#589518 | #6810. Array Concatenation | Sunlight9# | WA | 9ms | 6460kb | C++20 | 1.6kb | 2024-09-25 18:14:35 | 2024-09-25 18:14:36 |
Judging History
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'