Solution

题目给的 范围极大，只能直接计算出答案，预处理递推都不行。
这样思考之后，我们先考虑2个位置的情况，只有前面是1，后面是0，才存在一对逆序对。
3个位置情况下，前面是1，后面是0，存在3种情况，那么还剩一个位置。
这个位置可以选0或者1，这个位置逆序数的贡献会在下次枚举到这个点是1的情况累加到，为0则没有贡献。
那么到n个位置，我们可以知道，前面是1，后面是0，情况存在 种。
那么对于其他n-2个地方，存在0和1两种状态，共有
所以答案为 再根据快速幂和费马小定理，在 的时间算到答案

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline ll read() {
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == &#39;-&#39;) w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int MOD = 1e9 + 7;

ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)    (ans *= a) %= MOD;
        b >>= 1;
        (a *= a) %= MOD;
    }
    return ans;
}

int main() {
    ll n = read();

    // 不构成组合数，特判为0
    if (n == 0 || n == 1)    puts("0");

    // 利用费马小定理，除以素数a等于乘以a的逆元
    else {
        ll ans = ((((n % MOD * ((n - 1) % MOD)) % MOD) * (qpow(2, MOD - 2) % MOD) % MOD) * qpow(2, n - 2)) % MOD;
        printf("%lld\n", ans);
    }

    return 0;
}

pycode

MOD = 1000000007
n = int(input())
if n == 0 or n==1:    print(0)
else:    print(n*(n-1)//2*pow(2,n-2,MOD)%MOD)