【每日一题】17.逆序对 （快速幂 + 思维）

题目给的 (n le 1e18) 范围很大，即时预处理数据都不行、只能直接计算答案

想到这以后先考虑 (n = 2) 的情况，只有前面 (1) 后面是 (0) 才存在逆序对；

(n = 3) 时前面为 (1) 后面为 (0) 的情况有 (3) 种，但对于剩下的一个位置来说，可选 (0) 或 (1) ，但这个位置的逆序数贡献会在下次枚举至此点的情况才会累加，而 0 没有贡献

当存在 (n) 个位置时，我们首先需要保证一对逆序对，即前面为 (1) 后面为 (0) 的情况，情况数：(C_n^2) 种

而对于其他 (n-2) 个地方则都存在 (1) 或 (0) 共有 (2^{n-2})

所以最后答案为 (C_n^2· 2^{n-2})

using ll     = long long;
const ll mod = 1e9 + 7;
ll qpow(ll a, ll b) {
    ll ans = 1;
    for (; b > 0; b >>= 1, a = (a * a) % mod)
        if (b & 1) ans = (ans * a) % mod;
    return ans % mod;
}
void solve() {
    ll n;
    cin >> n;
    ll sum = (n % mod) * ((n - 1) % mod) / 2 % mod;
    ll p   = qpow(2, n - 2);
    cout << (p * sum) % mod << "
";
}