NC14731

题意

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

思路

题目让我们求逆序对，长度 $n$n的01子串1在0的左边有多少种方案，由于题中1和0的地位是等价的，故正序对的个数和逆序对个数是一样的。
$cn{t}_{逆序对}=\frac{cn{t}_{(正序对+逆序对)}}{2}$cnt逆序对​=2cnt(正序对+逆序对)​​
$cn{t}_{(正序对+逆序对)}={\sum }_{i=1}^{n-1}i(n-i)C_n^i=n(n-1)2^{n-2}$cnt(正序对+逆序对)​=∑i=1n−1​i(n−i)Cni​=n(n−1)2n−2
表示从 $n$n个数里选 $i$i个1剩下的全部为0，所构成的01子序列的个数。(这样的好处是不需要考虑正逆)
上面的数学公式递推需要用到: ${\sum }_{i=0}^n{C}_n^i=2^n$∑i=0n​Cni​=2n

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

ll n;

ll qpow(ll a,ll b,ll mod){
	ll ans=1;
	while(b>0){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	ll x=qpow(2,n-3,mod);
	ll y=(n%mod)*((n-1)%mod)%mod;
	if(n==2) cout<<1<<'\n';
	else cout<<x*y%mod<<'\n';
	return 0;
}