【每日一题】逆序对

戳我传送

solution：

大佬们一看到1e18就知道要找规律，本菜鸡还想着递推。
方法一：
刘大佬说可以在n个位置里找出2个组成1 0，有 种方案，其它位置有 种可能，答案就是* 。这太神仙了，递推菜鸡的我看了好久。刘大佬原话----0就是没有贡献，1的话会在选这个位置是1后面是0算到。
看了邓老师的题解后感觉自己傻到了，比刘大佬的说法更清楚，就是选出一对逆序对，他能对个01串做出贡献，而01的逆序对可以找出个，那有这个逆序对的01串里还有逆序对不用算吗，是不用的，已经在求别的方案的时候就算到了。
方法二：
可以枚举每个位置i的贡献，第i个位置为1时没有贡献，为0时的贡献为前i-1个位置1的个数，前i-1个位置有 种可能，因为1和0出现的概率是一样的，共有（i-1）/2个1， 个串包含这前i个数。
答案就是 (i-1) * =n(n-1) *

Code:

#include<bits/stdc++.h>
#define ll long long
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int mod = 1e9+7;
ll qpow(int a,int b) {
    ll ans=1;
    while(b) {
        if(b&1)    ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
}
int main() {
    ll n; js;
    cin>>n;
    if(n>2) {
        ll ans=n%mod*(n-1)%mod*qpow(2,n-3);
        cout<<ans<<endl;
    }
    else if(n==1)    cout<<"0\n";
    else    cout<<"1\n";
}