【每日一题】逆序对

链接：https://ac.nowcoder.com/acm/problem/14731
来源：牛客网

题目描述

求所有长度为n的01串中满足如下条件的二元组个数： 设第i位和第j位分别位，则。 答案对1e9+7取模。
输入描述:
输入一个n。
输出描述:
输出答案对取模
示例1

输入

3
输出

6

说明
备注:

要组成一对逆序对，那么随机从n个位置任取两个，前面位置放1，后面位置放0，就组成一个逆序对，所以简单的排列组合，答案为。n个位置固定了两个位置了，还剩下n-2个位置，每个位置可以放0或者1，所以有种可能，所以最后的答案为=，用快速幂+快速乘优化即可。要注意这里是，所以如果n==1/n==2的时候(n-3)就会小于0，所以要特判为0和1。 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
//#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=1e5+7;
const ll INF=1e10+9;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
inline ll qmul(ll x,ll y,ll p)
{
    ll z=(long double)x/p*y;
    ll res=(unsigned long long)x*y-(unsigned long long)z*p;
    return (res+p)%p;
}
inline ll qpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)res=qmul(res,a,mod);
        a=qmul(a,a,mod);
        b>>=1;
    }
    return res%mod;
}
ll n;
int main()
{
    scanf("%lld",&n);
    if(n==1)puts("0");
    else if(n==2)puts("1");
    else printf("%lld\n",qmul(qmul(qpow(2,n-3),n,mod),n-1,mod));
    return 0;
}

老规矩，官方题解奉上：
在这里插入图片描述
活动链接：https://ac.nowcoder.com/discuss/408534