[牛客每日一题]

NC14731 逆序对

---

NC14731 逆序对

题目描述

求所有长度为n的01串中满足如下条件的二元组个数：
设第i位和第j位分别位ai和aj（i

答案对1e9+7取模。

输入描述:

输入一个n。

输出描述:
输出答案对1e9+7取模

示例1

输入
3
输出
6
说明

备注:

n <= 10 ^ 18

思路:

n的范围太大, 需要更加巧妙的思路
刚开始的全排列各种组合的想法不大现实
那么可以反过来想,
可以枚举每个固定的逆序对在多少种排列中出现, 他们之和即为所有排列中逆序对之和

1. 从n个位置选取2个
2. 其余位置任意排列
3. 注意取模

即

---

c++实现

#include
using namespace std;

typedef long long LL;
const int M = 1e9+7;
LL quickMul(LL a, LL n)
{
    LL res = 1;
    while (n){
        if(n&1) res = res*a%M;
        a = a*a%M;
        n >>= 1;
    }
    return res;
}
LL mul(LL a, LL b)
{
    a%=M, b%=M;
    return a*b%M;
}
int main()
{
    LL n;
    cin >> n;
    if(n < 2) cout << "0";
    else if(n == 2) cout << "1";
    else cout << mul(quickMul(2, n-3),mul(n,(n-1)));
    return 0;
}

---

Python实现

mod = int(1e9+7)
n = int(input())
if n < 2:
    print(0)
else:
    print((pow(2, n-2, mod)*n*(n-1)//2%mod)%mod)