每日一题：逆序对

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

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

输入描述:
输入一个n。

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

我们考虑在这n个位置中任意选取两个位置，依照前后顺序放置1和0，那么无论其余n-2个位置怎么放置，都会对结果贡献1。那么我们就能得出结果是 。最开始有点不理解为什么不考虑其他位置随意放的问题，其实就是只考虑当前i，j位能贡献的对数，把所有 可能加到一块就好了。另外，需要特判一下1，还有计算组合数的时候，除法要用乘法逆元来做。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const LL mod=1e9+7;
int gcd_(int a,int b) {return b==0?a:gcd_(b,a%b);}
LL fpow(LL a,LL b) {
    LL res=1;
    while(b) {
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
int main() {
//    cout<<"Accepted!\n";
    LL n;
    cin>>n;
    if(n==1) cout<<0;
    else {
        LL ans=n%mod*((n-1)%mod)%mod*(fpow(2,mod-2)%mod)%mod;
//        LL ans=(n%mod)*(n-1)%mod/2%mod;
        ans=(ans*fpow(2,n-2))%mod;
        cout<<ans;
    } 
    return 0;
}