首页 > 代码库 > Codeforce 810C Do you want a date?
Codeforce 810C Do you want a date?
题意：
给定n个不重复的数， 求出这些数的所有子集， 然后设一个数Ni 为 第i个子集中，最大的数 - 最小的数。 然后将i个 Ni求和， 结果mod 1e9 + 7。
分析：
首先将n个数排列，生成一个单调的数列。
举个例子， 如 1 3 5 7 9。
可以看出 1 作为一个子集中最小的数会有 2^4 - 1 = 15种（1 和 3 5 7 9组合， 3 5 7 9任意的非空子集有2^4 - 1种） ， 作为最大的数有2^0 - 1 = 0(因为没有数比1小).
同理 9 作为一个子集中最小的数会有2^0 -1= 0 种， 作为最大的数有 2^4 - 1 = 15种。
再例如 3 ， 作为最小的数会有 2 ^ 3 - 1 = 7种， 作为最大的数会有2^1 -1 = 1种。
所以我们可以得出以下公式 ：
作为最大的种类数就是 pow(2,有多少个数在i的左边) -1
作为最小的种类数就是 pow(2,有多少个数在i右边) -1
a[i] *（ i作为最大的数种类 - i作为最小的数的种类），可以求出这个数对答案的影响， 把n个a[i]求出来就是答案。
由于个数会去到很大， 所以可以用快速幂加速.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 +5;
const int mod = 1e9 + 7;
int n;
long long a[maxn];
typedef long long ll;
ll quickmod(ll a, ll b, ll m)
{
ll ans = 1;
while (b)//用一个循环从右到左便利b的所有二进制位
{
if (b & 1)//判断此时b[i]的二进制位是否为1
{
ans = (ans*a) % m;//乘到结果上，这里a是a^(2^i)%m
b--;//把该为变0
}
b /= 2;
a = a*a%m;
}
return ans;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
}
sort(a+1,a+1+n);
long long ans = 0;
for(int i = 1; i < n/2+1; i++)
{
long long t = 0;
t += (a[i] * -(quickmod(2,n-i,mod) - quickmod(2,i-1,mod)));
t += (a[n+1-i] * (quickmod(2,n-i,mod) - quickmod(2,i-1,mod)));
t %= mod;
ans = (ans +t) % mod;
}
printf("%lld\n", (ans + mod) % mod );//ans可能为负， 需要+mod
}
Codeforce 810C Do you want a date?
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。