@[TOC]
传送

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format:%lld

题目描述

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

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

3

输出

6

说明
在这里插入图片描述
备注:
n <= 10^18^

题解：

就是一个求逆序对
我们看如果1后面有5个0，就能构成5个逆序对
也就是我们考虑任意两个位置，只要前面是1，后面是0，无论其他位置是什么数，都能构成一个逆序对。而这样的情况有多少种，就说明有多少逆序对
接下来我们就要用到组合排列
在n个位置任选两个位置的方案数C^2^n ,
其他n-2个位置就是放0和1，随便放，那就是n-2个2相乘，就是2^n-2^,所以总逆序对是C^2^n* 2^n-2^

C^2^n* 2^n-2^=n(n-1)/2 *2^n-2^= n *(n-1)2^n-3^

因为n可以很大，所以要用到快速幂
n=1要特判一下
我提交后一直卡在95%，原来当n=2时程序就死循环了，所以n=2也要特判

代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
typedef long long ll;

ll poww(ll a,ll b)
{
    ll sum=1;
    while(b)
    {
        if(b&1)sum=sum*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return sum;
}
int main()
{
    ll n;
    scanf("%lld",&n);
    if(n==1)
    {
        cout<<0;return 0;
    }
    if(n==2)
    {
        cout<<1;return 0;
    }
    cout<<( ( ( n%mod )* ( ( n-1 ) % mod ) %mod )*(poww(2ll,n-3)%mod))%mod<<endl;
}