逆序对

题意

给定n，求长度为n的01串的逆序对个数的和。

思路

设为长度为i的01串逆序对个数。则

所以

容易推出

复杂度

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define db double
#define mp make_pair
#define fi first
#define se second
#define de(a) cout << #a << " = " << a << endl

ll mod = 1e9 + 7;

ll qmi(ll a, ll b){
    ll ans = 1LL;
    while(b){
        if(b & 1) ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

int main()
{
    ll n;
    cin >> n; 
    if(n >= 2)
        cout << ((n % mod) * ((n - 1) % mod) / 2 % mod) * qmi(2LL, n - 2) % mod <<endl;
    else 
        cout << 0 << endl;

    return 0;
}