逆序对_牛客博客

题意

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

思路

设 $dp[i]$ 为长度为i的01串逆序对个数。则

$dp[i] = \begin{cases} dp[i - 1] & \text{第i位填1}\\\\dp[i - 1] + \sum_{k = 1}^{k = i - 1}kC_{i - 1}^{k}&\text{第i位填0}\end{cases}$

所以 $dp[i] = 2dp[i - 1] + \sum_{k = 1}^{k = i - 1}kC_{i - 1}^{k} = 2dp[i - 1] + (i - 1) * 2^{i - 2}$

容易推出 $dp[n] = 2^{n - 2}*C_{n}^{2}$

复杂度

$o(\log{n})$

代码

#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;
}