浅析 NC14731 逆序对（快速幂）（除数取模）

题目链接：

https://ac.nowcoder.com/acm/problem/14731

题面：

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

输入描述:
输入一个n。
输出描述:
输出答案对1e9+7取模

input: 
2
output:
6

解释：
0	000		0
1	001		0
2	010		1
3	011		0
4	100		2
5	101		1
6	110		2
7	111		0

output = 0 + 0 + 1 + 0 + 2 + 1 + 2 + 0 = 6

数据范围:
n <= 10^18

分析：

1. 边界情况：

举例观察：
0	0000	0
1	0001	0

2	0010	1
3	0011	0

4	0100	2
5	0101	1
6	0110	2
7	0111	0

8	1000	3
9	1001	2
10	1010	3
11	1011	1
12	1100	4
13	1101	2
14	1110	3
15	1111	0

n = 1	output : 0 
n = 2	output : 1
n = 3	output : 6
n = 4	output : 24

注意：f(0) = f(1) = 0

2. 数学推导——递推公式——求解得通项

假设 $f (n)$ 为满足题目要求的答案（所有长度为 $n$ 的 $01$ 串中满足条件的二元组个数）。 $f (n)$ 对应的最高位（首位）有两种情况：

若最高位（首位）为 $0$ ，则逆序对数由 $f (n - 1)$ 决定。
若最高位（首位）为 $1$ ，则逆序对数由 $f (n - 1)$ 加上 $n - 1$ 时的所有情况的 $0$ 出现的次数。一共有 $n - 1$ 个位置，每个位置有 0 1 两种情况， $n - 1$ 情况下长度为 $n - 1$ 的数字串的总数为 $2^{n-1}$ ，则所有的 0 1 数字的总数为 $(n-1) * 2^{n-1}$ ，其中，1 和 0 各占一半，因此 0 出现的总数为 $(n-1) * 2^{n-2}$ 。

综上，得到递推公式 $f(n) = 2 f(n-1) + (n-1)2^{n-2}$ 。
该递推公式可求解得到通项，不需要分治递归去做。

\begin{aligned} f(n) &= 2^1 f(n-1) + (n-1)2^{n-2} \\ &= 2(2f(n-1) + (n-2)2^{n-3}) + (n-1)2^{n-2} \\ &= 2^2 f(n-2) + (n-2)2^{n-2} + (n-1)2^{n-2} \\ &= ...... \\ &= 2^{n-2} f(2) + \sum_{i=1}^{n-2} (n-i) 2^{n-2} \\ &= 2^{n-1} f(1) + \sum_{i=1}^{n-1}(n-i) 2^{n-2} \\ &= \frac{n(n-1)}{2}2^{n-2} \end{aligned}

解得 $f(n) = \frac{n(n-1)}{2}2^{n-2}$ 。

3. 快速幂计算

由题目的数据范围 n <= 10^18，可知使用长整型并做 $2^{n-2}$ 的快速幂运算。

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

4.除数取模问题：

题目输出要求——答案模一个数，并且这个数往往是1000000007 (1e9 + 7)。
如果只有乘法和加法，那么我们对此毫无压力。
但是，除法出现时，我们往往需要用高精除法。
而 费马小定理 我们带来了福音！！！
我们再不用为了区区一个模1000000007而用高精除法了。 \

费马小定理：若p是质数，且a、p互质（整数a不是p的倍数），那么 $a^{p-1} \mod p = 1$ 。
tip1:质数（素数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
tip2:若N个整数的最大公因数是1，则称这N个整数互质。

现在，我们要求a/c mod p，通过一系列神奇的转化，那万恶的除法就会神奇地消失...

\begin{aligned} {a / c \mod p} &= a / c \mod p * 1 \\ &= a / c \mod p * c^{p-1} \mod p \\ &= a * c^{p-2} \mod p \end{aligned}

在本题，只要进行类似的替换即可 : $500000004 * 2 \equiv 1(\mod 1000000007)$

代码：

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long 
 
const ll p = 1e9+7;
 
ll quick_pow(ll a, ll b) {
    ll ans = 1;
     
    while (b) {
        if (b&1) 
            ans = ans*a % p;
        b >>= 1;
        a = a*a % p;
    }
    return ans;
}
int main () {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
     
    ll n;
    cin >> n;
     
    if (n <= 1) {
        cout << 0;
        return 0;
    }

    cout << ((((n%p) * ((n-1)%p))%p * 500000004 % p)*quick_pow(2, n-2))%p;
 
    return 0;
     
}

时间复杂度 O(logn)

空间复杂度 O(1)

// 小细节注意：
cout << (((((n%p)*(n-1)%p)%p)/2)*quick_pow(n-2))%p;  // error
//                           ^
//                     高精度除法的问题

cout << (n%p) * ((n-1)%p) % p * 500000004 % p * quick_pow(2, n-2) % p;   // ok   
    
cout << ((((n%p) * ((n-1)%p))%p * 500000004 % p)*quick_pow(2, n-2))%p;   // ok

cout << (( (n%p) * ((n-1)%p) %p * 500000004 % p)*quick_pow(2, n-2))%p;   // ok
//        ^                 ^  
//        这里少了括号，可以通过

cout << ((((n%p) *  (n-1)%p )%p * 500000004 % p)*quick_pow(2, n-2))%p;   // error
//                 ^       ^  
//      注意这里少了括号，结果只通过 13.64%  ->  (n%p) *  (n-1) 运算结果可能溢出


运算符优先级：
/ * % 同级，运算顺序从左往右

上面的只通过 13.64% 的情况是因为从右往左结合计算的过程中发生溢出，要勤加括号注意运算的结合顺序。


long long：
所占内存大小：8byte=64bit；
所能表示范围：-9223372036854775808~9223372036854775807；
(即-2^63 ~ 2^63-1)
（-9*10^18 ~ 9*10^18）

浅析 NC14731 逆序对 （快速幂）（除数取模）