做网站的空间和服务器sem工作原理
文章目录
- 题目描述
- 输入格式
- 输出格式
- 样例输入1
- 样例输出1
- 样例输入2
- 样例输出2
- 提交链接
- 提示
- 解析
- 参考代码
题目描述
你有一个由 n n n 个整数组成的数组 a a a 。
你要对它进行 k k k 次操作。其中一个操作是选择数组 a a a 的任意连续子数组(可能为空)，并在数组的任意位置插入该子数组的和。
你的任务是找出 k k k 次这样的操作后数组可能的最大和。
由于这个数字可能非常大，请输出取模为 1 0 9 + 7 10^9+7 109+7 的答案。
提示：数字 x m o d p x\mod\ p xmod p 的余数等于最小非负数 y y y，满足 x = p ⋅ q + y x=p⋅q+y x=p⋅q+y ( q q q 为整数)。
输入格式
第一行包含两个整数 n n n 和 k ( 1 ≤ n , k ≤ 2 ∗ 1 0 5 ) k(1 \leq n,k \leq 2*10^5) k(1≤n,k≤2∗105)—分别是数组的长度 a a a 和操作次数。
第二行包含 n n n 个整数 a 1 , a 2 , . . . , a n ( − 1 0 9 ≤ a i ≤ 1 0 9 ) a_1,a_2,...,a_n(-10^9 \leq a_i \leq 10^9) a1,a2,...,an(−109≤ai≤109)。
输出格式
输出一个整数—经过 k k k 次运算模数 1 0 9 + 7 10^9+7 109+7 后得到的数组最大和。
样例输入1
2 2
-4 -7
样例输出1
999999996
样例输入2
3 3
2 2 8
样例输出2
96
提交链接
https://hydro.ac/d/lp728/p/13
提示
样例解释 1 1 1:
在第一个测试用例中，最好在数组中取一个空子数组两次，并在任意位置插入空子数组的和 ( 0 ) (0) (0)，这样得到的数组和为 ( − 4 ) + ( − 7 ) + 0 + 0 = − 11 (-4)+(-7)+0+0=-11 (−4)+(−7)+0+0=−11，模数 1 0 9 + 7 10^9+7 109+7 为 999999996 999999996 999999996。
解析
核心：找到数组中总和最大的子数组。
设 s s s 表示为原始数组的总和， x x x 表示为原始数组中总和最大的子数组的总和。
k = 1 k=1 k=1 时，答案为 s + x s+x s+x； k = 2 k=2 k=2 时，答案为 s + x + 2 ∗ x s+x+2*x s+x+2∗x
任意 k k k ，具有最大和的子数组的和最初是 x x x ，然后是 2 ⋅ x 2⋅x 2⋅x ，然后是 4 ⋅ x 4⋅x 4⋅x ， … ， 2 k − 1 ⋅ x 2^{k−1}⋅x 2k−1⋅x
答案等于 s + x + 2 ⋅ x + ⋯ + 2 k − 1 ⋅ x = s + 2 k ⋅ x − x s+x+2⋅x+⋯+2^{k−1}⋅x=s+2^k⋅x−x s+x+2⋅x+⋯+2k−1⋅x=s+2k⋅x−x。
取余的时候要考虑负数的情况。若为负数可以先加上模数再进行取余。
参考代码
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 9 , mod = 1e9 + 7;
typedef long long ll;
int t , n , a[maxn] , k;
int main()
{ll ans = 0;cin >> n >> k;for(int i = 1; i <= n; i++){cin >> a[i];ans += a[i];}ans = (ans % mod + mod) % mod;ll sum = 0 , mx = 0;for(int i = 1; i <= n; i++) //区间最大和{sum += a[i];if(sum < 0)sum = 0;mx = max(mx , sum);}mx %= mod;ll two = 1;for(int i = 1; i <= k; i++)two = two * 2 % mod;ans = (ans + two * mx - mx + mod) % mod;cout << ans << endl;return 0;
}