【枚举】CF809A

以你之姓@ 2024-03-22 17:18 48阅读 0赞

[? - Virtual Judge (vjudge.net)][- Virtual Judge _vjudge.net]

题意：

在一个数轴上有n个点，每个点都有坐标

对于每次取的这些点的子集

![91a34df269364331ad644f9c6b4e277e.png][]

让我们求：

![612f9ab0cc564e9c887b39880135e35d.png][]

![20fca1e5d5fc490792d9879afb7737c4.png][]

![700b3b3d559d43969eda46e6f3e8e316.png][]

思路：

一开始想的是枚举长度+滑动窗口，但是是n^2的，肯定超

那么就是O(n)枚举+O(1)算贡献

O(n)算每一个数的贡献

一开始还有个想法就是枚举其中一个端点，然后O(1)计算以此为左端点的所有区间的贡献

事实上，想法差不多，但是贡献算错了

对于一个位置i，ai会被加(1<<i)次，会被减(1<<(N-i))次

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=3e6+10;
    const int mxe=3e5+10;
    const int mod=1e9+7;
    
    int N;
    int a[mxn];
    
    int ksm(int a,int b,int mod){
    	int res=1ll;
    	while(b){
    		if(b&1) res=(res*a)%mod;
    		a=(a*a)%mod;
    		b>>=1;
    	}
    	return res;
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	sort(a+1,a+1+N);
    	int ans=0;
    	for(int i=1;i<=N;i++){
    		ans=((ans+ksm(2,i-1,mod)*a[i])%mod+mod)%mod;
    		ans=((ans-ksm(2,N-i,mod)*a[i])%mod+mod)%mod;
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[- Virtual Judge _vjudge.net]: https://vjudge.net/contest/558206#problem/D
[91a34df269364331ad644f9c6b4e277e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/4b12511a0afa4543a3a9f0a105987326.png
[612f9ab0cc564e9c887b39880135e35d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/f2822d00d46a4463973781273f2d62af.png
[20fca1e5d5fc490792d9879afb7737c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/e66626bfa1d942d69bb4136137c06656.png
[700b3b3d559d43969eda46e6f3e8e316.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/76a5838439d7448b8914424bc68cf354.png