NC14731

题意

求所有长度为的01串中满足如下条件的二元组个数：
设第位和第位分别位和，则
答案对取模。

思路

题目让我们求逆序对，长度的01子串1在0的左边有多少种方案，由于题中1和0的地位是等价的，故正序对的个数和逆序对个数是一样的。

表示从个数里选个1剩下的全部为0，所构成的01子序列的个数。(这样的好处是不需要考虑正逆)
上面的数学公式递推需要用到:

#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;
}