逆序对（组合数学）

题目：

求所有长度为n的01串中满足如下条件的二元组个数：
设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。
答案对1e9+7取模。

做法：

由于到了。递推都做不了了，唯有推柿子大法。
考虑每一位和前面的位对答案的贡献。
第位上的0对答案无贡献。
第位上的1对答案的贡献是前位上0的数量。
前位形成个01串，每个串长。所以共有个数字。其中0和1各占一半！所以前位上0的数量：。而后面的位是0是1对当前第位的贡献没有影响，直接把乘进去即可。
所以第的贡献就是。(第i位上的1配上前i-1位上的0)
考虑每一位的贡献：
快速幂求解即可。
PS：特判掉。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
ll ksm(ll x, ll y){
    ll ans = 1;
    while (y){
        if (y&1) ans = ans*x%mod;
        x = x*x%mod;
        y >>= 1;
    }
    return ans;
}
ll mul(ll x, ll y){
    x %= mod, y %= mod;
    return x*y%mod;
}
int main(void){
    IOS;
    ll n; cin >> n;
    if (n <= 1) cout << 0 << endl;
    else if (n == 2) cout << 1 << endl;
    else cout << mul(mul(n, n-1), ksm(2, n-3)) << endl;
    return 0;
}