【每日一题】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 << "\n";
}

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

原文：https://www.cnblogs.com/RioTian/p/14715494.html