逆序对_牛客博客

题意：给定长度 $n$ ，问可以得到的 $a[i]=1,a[j]=0,i<j$ 序列个数。
题解： 先考虑了很久没看数据范围，看到 $n <= 10^{18}$ 后开始找技巧。
首先考虑枚举每种逆序对的个数, 任取 $i<j<=n$ ，那么使 $a[i]=1,a[j]=0$ 对答案的贡献就是 $2^{n-2}$ ，因此只要任取两个合法位置即可即 $C_n^2$ 。则答案就是 $C_n^2\times2^{n-2}$
自然有模则想到快速幂，对于 $C_n^2=\frac{(n-1)\times n}{2}$ 的计算，如果直接做必然要考虑逆元，那么这里可以先除 $2$ 后再取模乘可以避免求逆元。
注意坑点当n=1时直接考虑答案为0，代入快速幂后会死循环。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;

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

int main()
{
    ll n; scanf("%lld", &n);
    if(n == 1) return 0 * printf("0\n");
    ll a = n, b = n - 1;
    if(a & 1) swap(a, b);
    a /= 2;
    ll res = a % mod * (b % mod) % mod;
    res = res * qp(2, n - 2) % mod;
    printf("%lld\n", res);

    return 0;
}