题意: 首先定义集合的F值为 这个集合里面最大值和最小值的差。 现给出一个拥有n个数的集合(没有相同的元素), 要求求出这个集合内所有子集的F的值的和。例如: {4、7}这个集合里面有子集{4}、{7}、{4, 7}, 则这些子集的F值分别为4-4=0、7-7=0、7-4=3, 所以最后的结果就是0+0+3 = 3！
以下分析引用至 : http://blog.csdn.net/dragon60066/article/details/72599167
分析: 不难想到要先使数组升序方便计算和思考, 然后观察发现如果选定任意一头一尾两个元素, 假如为ai、aj (ai<aj) 那这个两个元素之间围起来的区间可以看成ai....aj这样的数集, 且这集合里面所有子集贡献的F值都等于 aj - ai, 那这个区域包含了多少个这样的F值的集合呢？用笔简单列出表后不难发现规律, 这个和为个(需要用到快速幂), 至于具体为什么, 可以看自己多加思考一下且在参考博客有说明。当时想到这个后马上打出了枚举程序
#include<bits/stdc++.h>
#define LL long long
using namespace std;
;
LL arr[];
LL mi[];
LL qmod(LL a, LL b, LL c)
{
LL ans = ;
while(b){
) ans = (ans*a)%c;
a = (a*a)%c;
b >>= ;
}
return ans;
}
int main(void)
{
int n;
scanf("%d", &n);
; i<n; i++){
scanf("%lld", &arr[i]);
}
sort(arr, arr+n);
LL sum = ;
LL temp;
; i<n; i++){
mi[i] = qmod(, i, mod);
}
; i<n-; i++){
; j>i; j--){
LL sub = arr[j] - arr[i];
!=)temp = mi[j-i-];
;
temp%=mod;
sum += (((temp%mod)*(sub%mod))%mod)%mod;
sum%=mod;
}
}
printf("%lld\n", sum);
;
}然后就可以顺利超时了, 因为像我这样做的复杂度是O(n^2)！需要优化！于是上网搜索看到了前缀和的解法, 甚是巧妙, 而且貌似榜上大佬大多也是这样做！
引用一下——>进一步思考，对于每个i, j，取值可能有
，第一种前面系数是(a[2]-a[1]+a[3]-a[2]+...+a[n]-a[n-1])=a[n]-a[1]，同理可以发现第二种是a[n]+a[n-1]-a[1]-a[2]......，那么就推出来了：
那这个直观一点的话到底是在干什么玩意呢？看下面根据描述打出来的表
看到规律了吧！发现系数是对称的, 那我们根据系数的规律枚举从0到n-2的2次方就行了！不过细想的话, 虽然是找到了系数的规律, 但是好像还是不好实现, 参考别人的程序看到别人使用了前后缀和的做法, 巧妙的完成了依据上面规律进行的枚举操作, 具体的话不好说, 看一下程序便知！
以下为拙略表达, 可以跳过: 不过我还是说一下, 按我的理解就是从前面到中间的系数(以n=6为例, 枚举从2^0到2^2的系数)倒是不难枚举出来, 但是后面的就略微麻烦了, 解决方法——>定义前后缀和(例:sumf[i]是从1到i的前缀和, sumb[i]是n-1到i的后缀和), 那还是以n=6为例, 2^0到2^2的系数分别可以用sumb[6] - sum[1] 、 sumb[5]-sumf[2]、 sumb[4]-sumf[3]来解决, 后面的2^3 可以 sumb[3] - sumf[4], 停！有没有发现 计算这个差的过程中实际就是 a6+a5+a4+a4-a4-a3-a1-a2！ a3和a4巧妙的被约去了, 2^4的计算也是同样道理！类似于回文？好思想！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
;
;
LL arr[maxn], sumf[maxn], sumb[maxn], mi[maxn];
LL quick_mod(LL a, LL b, LL c)
{
LL ans = ;
while(b){
) ans = (ans*a)%c;
a = (a*a)%c;
b >>= ;
}
return ans;
}
int main(void)
{
int n;
scanf("%d", &n);
; i<=n; i++)
scanf("%d", &arr[i]);
sort(arr+, arr++n);///使序列单调
sumf[] = sumb[n+] = ;
mi[] = ;
; i<n-; i++)
mi[i] = quick_mod(, i, mod);///二的次方数组
; i<=n; i++)
sumf[i] = sumf[i-] + arr[i];///前缀和
; i--)
sumb[i] = sumb[i+] + arr[i];///后缀和
LL ans = ;
; i<n; i++){ //实际就是0 -- n-2 次循环
LL temp = (-sumf[i] + sumb[n-i+])%mod;
ans = (ans%mod + (temp * mi[i-])%mod)%mod;
}
printf("%lld\n", ans);
;
}