怎么创建网站免费的,开发网站能赚多少钱,注册安全工程师查询官网,成都小程序商城开发链接#xff1a;
2681. 英雄的力量
题意#xff1a;
对于一个序列可以得到一个值max^2 * min#xff0c;求一个数组的所有子序列数值和
解#xff1a;
快速幂和慢速乘暴力 TLE(2558 / 2584)
首先对于这个数组来说#xff0c;求值只依靠序列的最大值和最小值#xf…链接
2681. 英雄的力量
题意
对于一个序列可以得到一个值max^2 * min求一个数组的所有子序列数值和
解
快速幂和慢速乘暴力 TLE(2558 / 2584)
首先对于这个数组来说求值只依靠序列的最大值和最小值并且所有子序列都要求所以我们先将数组排序
对于每次遍历到的数字nums[i]都有一个nums[i]^3加入到ans里表示子集[i,i]子集[l,r]表示以L为最小值R为最大值的子集
同时我们还要计算[0,i],[1,i]......[i-1,i]我们可以发现子集[l,r]的值的和是nums[r]^2 * nums[l] * 2^r-l-1因为l和r之间有r-l-1个数字每个数字都有选与不选两种状态且不影响子集[l,r]的值那我们可以发现每当R右移1它所需要乘上的每个nums[l]就要翻一倍所以我们使用一个变量来累积他所需要乘的数值
例如nums[1],nums[2],nums[3]
对于nums[1]我们只需要求nums[1]^3
对于nums[2]需要nums[2]^3 nums[2]^2 * nums[1] * 1
对于nums[3]需要nums[3]^3 nums[3]^2 * nums[2] *1 nums[3]^2 *nums[1] * 2
这个nums[3]除了nums[3]^3剩下的nums[3]^2 * nums[2] *1 nums[3]^2 *nums[1] * 2可以转化为(nums[3]^2)*(nums[2] 2* nums[1])。
以此类推下一个就是(nums[4]^2)*(nums[3] 2* nums[2] 4* nums[1])。
实际代码
#includebits/stdc.h
using namespace std;
constexpr static long long Mod1E97;
long long msc(long long base,long long up)
{//coutbaseupupendl;long long ret0;while(up){if(up1) retbase;basebase;base%Mod;ret%Mod;up1;}return ret;
}
long long msm(long long base,long long up)
{//coutbasemsmupupendl;long long ret1;while(up){if(up1) ret*base;basemsc(base,base);base%Mod;ret%Mod;up1;}return ret;
}
int sumOfPower(vectorint nums)
{sort(nums.begin(),nums.end());long long ans0,after0;int lgnums.size();for(int i0;ilg;i){ansmsm(nums[i],3);ansmsm(nums[i],2)*after;after*2;afternums[i];after%Mod;ans%Mod;}return ans;
}
/*
int sumOfPower(vectorint nums)
{sort(nums.begin(),nums.end());long long ans0;int lgnums.size();for(int i0;ilg;i){for(int ji;jlg;j){//couti:i j:jendl;if(ij) ansmsm(nums[i],3);else{ansmsc(msc(msm(nums[j],2),nums[i]),msm(2,j-i-1));}ans%Mod;}}return ans;
}*/
int main()
{vectorint nums;int num;while(cinnum)nums.push_back(num);int anssumOfPower(nums);coutansendl;return 0;
}限制
1 nums.length 1051 nums[i] 109
