逆序对_牛客博客

链接：https://ac.nowcoder.com/acm/problem/14731
来源：牛客网
题面
求所有长度为 $n$ 的 $01$ 串中满足如下条件的二元组个数：
设第i位和第j位分别位 $ai$ 和 $aj$ （ $i<j$ ），则 $a_i = 1,a_j = 0$ 。答案对 $10 ^ 9 + 7$ 取模。

$solution$
考虑一对 $1$ 和 $0$ 在多少情况下可以出现，即是这对 $1$ 和 $0$ 的贡献钦定两个位置，剩下随便选， $2 ^ (n-2)$ 再考虑钦定哪两个位置， $n \times (n-1) / 2$ 相乘即得 $2 ^ {n-3} \times n \times (n-1)$

$code$

#include <bits/stdc++.h>
#define ri int
#define ll long long
using namespace std;
const ll Mod=1e9+7;
inline ll ksm(ll a,ll b) {
    ll ans=1;
    while(b) {
        if(b&1)ans=ans*a%Mod;
        a=a*a%Mod;
        b>>=1;
    }
    return ans;
}
ll n;
int main() {
    scanf("%lld",&n);
    if(n==1)return !printf("0\n");
    if(n==2)return !printf("1\n");
    printf("%lld\n",ksm(2,n-3)*(n%Mod)%Mod*((n-1)%Mod)%Mod);
    return 0;
}