60很顺利:
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=200010;
const ll mod=1000000007;
ll a[maxn],r[maxn];
ll q_m(ll a,ll b){
ll ret=1;
while(b>0){
if(b&1){
ret*=a%mod;
ret%=mod;
}
a*=a%mod;
a%=mod;
b>>=1;
}
return ret;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=0;i<=n;++i)r[i]=q_m(2,i);
sort(a+1,a+n+1);
ll ans=0;
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
ans+=((a[j]-a[i])*r[j-i-1])%mod;
ans%=mod;
}
}
cout<<ans;
return 0;
}
预处理一些新的就行了
请问我模错在哪????
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=200010;
const ll mod=1000000007;
ll a[maxn],r[maxn],k[maxn];
ll q_m(ll a,ll b){
ll ret=1;
while(b>0){
if(b&1){
ret*=a%mod;
ret%=mod;
}
a*=a%mod;
a%=mod;
b>>=1;
}
return ret;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=0;i<=n;++i)r[i]=q_m(2,i);
k[0]=1;
for(int i=1;i<=n;++i)k[i]=(k[i-1]+r[i])%mod;
sort(a+1,a+n+1);
ll ans=0;
int sum=0;
for(int j=2;j<=n;++j){
sum+=((a[j]-a[1])*r[j-2])%mod;
sum%=mod;
}
for(int i=1;i<=n;++i){
ans=(sum+ans)%mod;
if(n-i-2==-1)break;
sum-=(a[i+1]-a[i]);
sum/=2;
sum=(sum%mod+(a[i]-a[i+1])*k[n-i-2]%mod+mod)%mod;
}
cout<<ans;
return 0;
}