逆序对（组合数+快速幂+快速乘）

题目地址：https://ac.nowcoder.com/acm/problem/14731
首先 先介绍一个组合数的公式及其证明过程（高中学的）：

然后我们假定f（n） 代表当前长度为n的01串中符合条件的二元数组的个数，
那么我们可以列出一个式子（稍后解释）
f(n+1)=2f(n) +1C(1,n)+2C(2,n)+3C(3,n)+......+nC(n,n)
好了 现在我们来解释一下这个式子
首先 对于一个长n+1的01串我们可以看成一个 长为n的01串 在末尾加了一个数字0或1后所形成的式子
首先在末尾添加1 形成的新01串 的结果 和不添加 是没有任何区别的 因为在末尾的1 起不到任何作用，所以添加1后的串 所有的满足条件的二元数组的个数就是f（n）
然后在末尾添加0 的情况 ：
添加0以后，不会影响长为n的01串满足条件的个数，那么我们来思考一下多出了哪些个数。
多出的个数其实就是长为n的01串中1的情况
所以分为长为n的01串中有1个1 2个1 3个1 直到n个1
多出了的情况也就是 1C(1,n)+2C(2,n)+3C(3,n)+......+nC(n,n)
将以上情况汇总得到
f(n+1)=2f(n) +1C(1,n)+2C(2,n)+3C(3,n)+......+nC(n,n)
然后根据最开始的公式化简得到
f(n+1)=2f(n) +n2^（n-1）
然后用高中的数列知识推出通项
f（n）=(2^（n-3))n(n-1)

由于这个n很大 要达到1e18
所以要用快速幂 和快速乘才能过这个题

#include<iostream>
#include<algorithm>
#include<set>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
#define close_stdin  ios::sync_with_stdio(false)
#define P pair<int,int>
typedef long long LL;
const int maxn = 0;
const LL mod = 1000000007;//1e9+7   之所以写成这样是因为 1e9+7 vs总是报错 我也很烦恼  总有一天要跳槽取用codeblock
// 当a和b 接近 1e18 的时候 就要用到快速乘了  不然很难
//快速乘
LL ksc(LL a, LL b, LL mod)//快速乘
{
    LL ans = 0;
    a %= mod;
    while (b > 0)
    {
        if (b & 1) ans = (ans + a) % mod;
        b >>= 1;//位运算，右移1位，相当于除以2
        a = (a + a) % mod;
    }
    return ans;
}
//用于解决 （a^b ）% mod 的问题
//当a，b接近1e9的时候 就需要用到快速幂了  不然可能会有点吃力  
//快速幂  
LL ksm(LL a, LL b, LL mod)//快速幂
{
    LL ans = 1;
    a %= mod;
    while (b > 0)
    {
        if (b & 1) ans = ksc(ans, a, mod) % mod;
        b >>= 1;//位运算，右移1位，相当于除以2
        a = ksc(a, a, mod) % mod;
    }
    return ans;
}
int main()
{
    close_stdin;
    LL n;
    cin >> n;
    if (n <= 1) { cout << "0\n"; }
    else if (n == 2) { cout << "1\n"; }
    else if (n == 3) { cout << "6\n"; }
    else {
        LL ans = ksc(ksc(ksm(2, n - 3, mod), n, mod), n - 1, mod);
        cout << ans << "\n";
    }

}

谢谢浏览