【每日一题】逆序对

题目

题目描述:

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

输入描述:
输入一个n。

输出描述:

输出答案对1e9+7取模

备注:

n <= 10¹⁸

解析

这题目，一看到串长最大可以是18位数就肯定不正常。

所以首先想到的就是把规律（公式）找出来。

因为串超长所以就来找每一位的贡献。

当a_i为1时，该位则可能有贡献，否则直接舍去
找较大位和较小位和a_i位之间的关系
因为题目中i<j，所以a_j是较小位（在a_i的后面）

较大位：较大位与二元组没有关系，只会影响到排列组合，大小为 $2^{n-1}$ 。

较小位：较小位要考虑到形成条件（取0时才可计数）。因为较小位有i-1位数，所以有2^i-1种01串，同时串长为i-1。又以为0和1共占总数的一半，所以大小为 $\frac{1}{2}$ $\times$ $2^{i-1}$ $\times\left( i-1\right)$ 。

由较大位和较小位可的每一位的值为 $\left( i-1 \right)\times2^{n-2}$ 。

所以每一位加起来得到 $0\times2^{n-2}+……+(n-1)\times2^{n-2}=n\times(n-1)\times2^{n-3}$

求出公式以后只要快速幂就行了。。。（算个公式累死本憨憨了）

AC代码

#include <iostream>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const int mod = 1e9 + 7;

ll mypow(ll down, ll up);//快速幂

int main() {
    js;
    ll n; cin >> n;
    cout << (n % mod) * ((n - 1) % mod) * mypow(n % mod, n - 3) % mod << endl;
    return 0;
}

ll mypow(ll down, ll up) {
    ll mul = 1;
    while (up) {
        if (up & 1) mul = mul * down % mod;
        up >>= 1;
        down = down * down % mod;
    }
    return mul;
}

后期补充

邓老师给的超简单理解方法：

任选两个位置的方案数是 $C_{n}^{2}$ ，其他n个位置随便放的方案数是 $2^{n-2}$ ，所以总逆序对数就是 $C_{n}^{2}2^{n-2}$ 。