逆序对 来源 Wannafly挑战赛6

题意：
给一个计算所有长度为n的01序列的贡献和，每个序列的贡献为对数满足
题解：
我们来考虑第位为对答案产生的贡献。那么对于特定的序列，若就对答案产生贡献，那么的序列就会有个，而要使就有组，因此第位为对答案产生的贡献为
因此答案为
代码：

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int MX=750008;
const int mod=1e9+7;
const double eps=1e-6;
const double pi=3.14159265358979;
using namespace std;
ll qpow(ll a,ll b,ll MOD=mod){for(ll ans=1;;a=a*a%MOD,b>>=1){if(b&1)ans=ans*a%MOD;if(!b)return ans;}}
ll inv(ll a,ll MOD=mod){return qpow(a,MOD-2,MOD);}
ll __gcm(ll a,ll b){return a*b/__gcd(a,b);}
int main()
{
  ios::sync_with_stdio(0),cin.tie(0);
  ll inv2=inv(2);
  ll n;
  cin>>n;
  if(n==0||n==1)cout<<0<<endl;
  else cout<<n%mod*((n-1)%mod)%mod*inv2%mod*qpow(2,n-2)%mod<<endl;
}