【组合数学】codeforces C. Do you want a date?

codeforces.com/contest/810/problem/C

【题意】

给定一个集合A，求

，

输入：

【思路】

基数为n的集合有2^n-1个非空子集。

首先n个数要从小到大排序，枚举最后的集合中最大和最小的元素是a[i]和a[j](i< j);
则f值是a[j]-a[i]的集合有2^(j-i-1)个; 然后答案+=(a[j]−a[i])*2^(j-i-1);

这样时间复杂度是O(n^2)。

我们可以把各项组合一下，把2^i提取出来。

比如考虑系数为
2^1的
必然是
a[3]-a[1]
a[4]-a[2]
a[5]-a[3]
…
a[n]-a[n-2]
=sum[n]-sum[i+1]-sum[n-i-1];

sum[i]是a[i]的前缀和。

这样对于[0,n-2]枚举2^i,时间复杂度是O(n),加上排序，总的时间复杂度是O(nlogn)

【注意】

sum[i]是取余后的结果，所以sum[n]-sum[i+1]-sum[n-i-1]可能是负数，要(+mod)%mod

【Accepted】

 #include <iostream>

 #include <stdio.h>

 #include <cmath>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <string>

 #include <bitset>

 #include <ctime>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 const int maxn=3e5+;

 const ll mod=1e9+;

 int a[maxn];

 int n;

 ll sum[maxn];

 ll two[maxn];

 void Init()

 {

     two[]=;

     for(int i=;i<=maxn;i++)

     {

         two[i]=(two[i-]*)%mod;

     }

 }

 int main()

 {

     Init();

     while(~scanf("%d",&n))

     {

         memset(sum,,sizeof(sum));

         for(int i=;i<=n;i++)

         {

             scanf("%d",&a[i]);

         }

         sort(a+,a+n+);

         for(int i=;i<=n;i++)

         {

             sum[i]=(sum[i-]+(ll)a[i])%mod;

         }

         ll ans=;

         for(int i=;i<=n-;i++)

         {

             ans=(ans+two[i]*(sum[n]-sum[n-i-]-sum[i+]+mod)%mod)%mod;

         }

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

【组合数学】codeforces C. Do you want a date?

最新文章

热门文章

巴特西

【组合 数学】codeforces C. Do you want a date?

最新文章

热门文章

【组合数学】codeforces C. Do you want a date?