每日一题4.16 逆序对

图片说明

思路：本题主要要想到将问题转化，我们可以看到，n的取值范围实在是太大了，所以我们要将问题转化如果我们先使其满足条件，即每一个满足的字符串中肯定有一个1在左边，0在右边。那么，我们怎么找呢？就是用 $图片说明$ ，就是从n个位置中会找到2个位置前放1，后放0的一共有几种情况。找到了这个之后，对于 $图片说明$ 里面的每一种情况，我们已经确保了它是一个符合的01串，然后现在就要考虑的是如何填充剩余的n-2个位置，显然，当然是随便放0或1进去就行了。所以就总共有 $图片说明$ 种不同的满足条件的01串.现在，我们就要做的是如何求出这个式子。因为n十分的大，所以我们先求 $图片说明$ ，也就是 $图片说明$ ,但是显然如果直接就这样算分子的话，有可能会超出longlong范围，所以，我们显然分子的两个式子对1e9+7求模，在进行乘法。接下来，就是求 $图片说明$ ，这个就是用矩阵快速幂的方法来求。

ll binarypow(ll a,ll b){  //记住是返回longlong型
    if(b==0)  return 1;
    if(b&1)  return a*binarypow(a,b-1)%mod;  //如果幂是奇数的话，让前面乘一个a，然后幂减1
    else{
        ll mul=binarypow(a,b/2);  //幂为偶数，那么就b/2，这里体现的就是分治的思想
        return mul*mul%mod;
    }
}

代码

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll binarypow(ll a,ll b){
    if(b==0)  return 1;
    if(b&1)  return a*binarypow(a,b-1)%mod;
    else{
        ll mul=binarypow(a,b/2);
        return mul*mul%mod;
    }
}
int main(){
    ll n;
    cin>>n;
    if(n==1)  cout<<"0"<<endl;  //这种情况单独考虑
    else{
        ll ans;
        ll t1=n%mod,t2=(n-1)%mod;  //对n，n-1求模后再相乘
        ans=t1*t2/2%mod;
        ll temp=binarypow(2,n-2);
        ans=ans*temp%mod;  //记住最后还要mod一下
        cout<<ans<<endl;
    }
    return 0;
}