【牛客每日一题】4.16 逆序对 ( 数学 , 排列组合 ,快速幂 , 快速乘 )

【每日一题】逆序对

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

题目描述

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

输入

3
输出

说明
备注:
$n < = 1 0^{18}$

要组成一对逆序对，那么随机从n个位置任取两个，前面位置放1，后面位置放0，就组成一个逆序对，所以简单的排列组合，答案为 $C (n, 2)$ 。n个位置固定了两个位置了，还剩下n-2个位置，每个位置可以放0或者1，就有 $2^{n - 2}$ 种可能，所以最后的答案为 $C (n, 2) * 2^{n - 2}$ = $n * (n - 1) * 2^{n - 3}$ ，用快速幂+快速乘优化即可。要注意这里是 $2^{n - 3}$ ，所以如果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