题目大意

求所有 长的 01 序列的逆序对数之和。

题解

一种方法是考虑所有 对，其中 。这必然产生一个逆序对。对于其他位置则没有要求，因此这个对的贡献为 。总共有 种这样的对，因此答案为 。

另一种方式是 DP。取 为长为 时的答案，则 。这似乎是一个可以求解的递归式，取 ，那么可以解出 。从而答案和上面相同。

#include <bits/stdc++.h>
#define INF 2000000000
#define M 1000000007
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
ll n;
int poww(int a, int b){
    int res = 1;
    while (b > 0){
        if (b & 1) res = 1ll * res * a % M;
        a = 1ll * a * a % M;
        b >>= 1;
    }
    return res;
}
void init(){
    cin >> n;
}
void solve(){
    if (n <= 1){
        cout << 0 << endl;
        return ;
    }
    int res = poww(2, (n - 2) % (M - 1));
    res = 1ll * res * poww(2, M - 2) % M;
    res = 1ll * (n % M) * res % M;
    res = 1ll * ((n - 1) % M) * res % M;
    cout << res << endl;
}
int main(){
    init();
    solve();
    return 0;
}