【每日一题】逆序对

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

题目描述

求所有长度为n的01串中满足如下条件的二元组个数: 设第i位和第j位分别位 a i a j i < j ai 和 aj(i<j) aiaji<j,则 a i = 1 , a j = 0 a_i=1,a_j=0 ai=1,aj=0。 答案对1e9+7取模。
输入描述:
输入一个n。
输出描述:
输出答案对 1 e 9 + 7 1e9+7 1e9+7取模
示例1

输入

3
输出

6

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

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