腾讯 云上做网站教程,行知智网站开发,长沙定制网页设计,广州市住房和城乡建设厅网站文章目录 题目描述输入格式输出格式样例输入1样例输出1样例输入2样例输出2提交链接提示 解析参考代码 题目描述
你有一个由 n n n 个整数组成的数组 a a a 。
你要对它进行 k k k 次操作。其中一个操作是选择数组 a a a 的任意连续子数组(可能为空)#xff0c;并在数组的… 文章目录 题目描述输入格式输出格式样例输入1样例输出1样例输入2样例输出2提交链接提示 解析参考代码 题目描述
你有一个由 n n n 个整数组成的数组 a a a 。
你要对它进行 k k k 次操作。其中一个操作是选择数组 a a a 的任意连续子数组(可能为空)并在数组的任意位置插入该子数组的和。
你的任务是找出 k k k 次这样的操作后数组可能的最大和。
由于这个数字可能非常大请输出取模为 1 0 9 7 10^97 1097 的答案。
提示数字 x m o d p x\mod\ p xmod p 的余数等于最小非负数 y y y满足 x p ⋅ q y xp⋅qy xp⋅qy ( 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^97 1097 后得到的数组最大和。
样例输入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)00-11 (−4)(−7)00−11模数 1 0 9 7 10^97 1097 为 999999996 999999996 999999996。
解析
核心找到数组中总和最大的子数组。
设 s s s 表示为原始数组的总和 x x x 表示为原始数组中总和最大的子数组的总和。 k 1 k1 k1 时答案为 s x sx sx k 2 k2 k2 时答案为 s x 2 ∗ x sx2*x sx2∗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 sx2⋅x⋯2^{k−1}⋅xs2^k⋅x−x sx2⋅x⋯2k−1⋅xs2k⋅x−x。
取余的时候要考虑负数的情况。若为负数可以先加上模数再进行取余。
参考代码
#includebits/stdc.h
#includealgorithm
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;
}
