逆序对

题意:给出一个长度为n的“01”串，问:统计所有01串的逆序对总数

分析： 首先对于逆序对，满足 设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。
只有当出现 1 0 这种样子串，才会对结果造成影响，所以先从n个中选出2个。
剩下n-2个数就有2^(n-2)种情况，也就是这几种情况会有贡献。
所以ans=C(n,2)*2^(n-2)

细节的话就是取mod，不要漏取mod，很容易炸

下面给出2中写法，一种是常规求组合数，用逆元+费小马定理。因为题目比较特殊，上面的ans可以化简成ans=（n-1）n2^(n-3) 所以第二种没必要用逆元

第一种：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

ll n;

int main()
{
    while(~scanf("%lld",&n))
    {
        if(n==1)
        {
            printf("0\n");
            continue;
        }
        if(n==2)
        {
            printf("1\n");
            continue;
        }
        //C(n,2)*2^(n-2)
        //     a/b%mod== a*(b的逆元)%mod 
        //     b的逆元%mod=pow(b,mod-2)
        ll a=((n%mod)*((n-1+mod)%mod))%mod;
        ll c=((a%mod)*(powmod(2ll,mod-2ll)%mod))%mod;
        ll ans=((c%mod)*(powmod(2ll,n-2ll)%mod))%mod;
        printf("%lld\n",ans%mod);
    }
    return 0;
}

第二种

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

ll n;

int main()
{
    while(~scanf("%lld",&n))
    {
        if(n==1)
        {
            printf("0\n");
            continue;
        }
        if(n==2)
        {
            printf("1\n");
            continue;
        } 
        ll ans=((((n%mod)*((n-1+mod)%mod))%mod)*powmod(2ll,n-3)%mod)%mod;
        printf("%lld\n",ans%mod);
    }
    return 0;
}