NC14731 逆序对

题意

在长度为n的01串中，若第i位=1，第j位=0，i<j，则成这是一对逆序对，求所有的长度为n的01串中一共能出现多少逆序对

思路一

枚举逆序对出现位置的方案

以 为例，逆序对可能的存在方案有：
、 、 三种方案（ )，每种方案中含一个 代表未知数字，这个未知数字又只能是0或1，所以共有 个逆序对

可能存在的疑惑
只有我这种菜鸡会有这样的疑惑吧
可能会想，在 、两个逆序对存在方案种，会存在某01串同时满足两种方案，比如这里的 ，这样计算会不会把一个逆序对计算两边呢？

其实 中的第一个1和0、第二个1和0各自是一个逆序对，分别对应了那两种逆序对存在方案，也就是说，一个逆序对存在方案只记录了两个逆序对中的一个，所以并不会出现重复计算的情况

思路二（并不完善，不会写了）

找规律
说一下我找规律的过程

记 为所有长度为n的01串中逆序对的个数

时：

时：

时：

不难发现，每当 时，新的01串就是在原有的01串左边加上0或1，让01串数量翻倍。数量翻倍以后，因为是在原有的01串的最左边加了一个数字，所有右边部分仍然有原先两倍多的逆序列。同时，因为有一部分新的01串时在旧01串左边加了1，这会根据原有01串中0的数量增加新的逆序对。
也就是说，
因为0和1出现的次数其实是一样的，所以我们的公式可以写为：

运用待定系数法构造等比数列以后 应该 可以得到f(n)关于n的公式 但是我不会，只能交给聪明的你了

代码

*需要用到快速幂取余

#include <iostream>

#define ull unsigned long long
using namespace std;

const ull m = 1e9 + 7;

ull myPow(ull a, ull x, ull mod) {
    ull res = 1;
    while (x) {
        if (x & 1) res = res * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return res;
}

int main() {
    ull n;
    cin >> n;
    if (n == 2) {
        cout << "1";
        return 0;
    }
    ull a = ((n % m) * ((n - 1) % m)) % m;
    ull b = myPow(2, n - 3, m);
    cout << (a * b) % m;
}