【组合数学 or 枚举】逆序对

朱雀 2024-03-17 16:10 54阅读 0赞

[C-逆序对\_Wannafly挑战赛6 (nowcoder.com)][C-_Wannafly_6 _nowcoder.com]

题意：

![6b6a311ffd974ffea068ef9f9f612fbe.png][]

思路：

组合数学，无非两种做法，一种是计数DP，另一种是组合数

DP显然不可能，那就组合数

考虑组合数的时候可以把这道题变成一个枚举题

我们去枚举位，一共最多1e18位（不是指真的枚举，是按位去计算贡献）

对于一个位，贡献这样计算：

![e65b5f35cb0e4589b92c3cfbc80f8001.png][]

![07eb184940c703ac2904d1ab54291de7.png][]

化简一下就是（等差数列）：

![f2a66d9a3f2cb8b40db7dd4b012079b9.png][]

![3f128e405caacc8270f2d3d58417c67c.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    
    int n;
    int ksm(int a,int b){
        int res=1;
        while(b){
            if(b&1) res=(res*a)%mod;
            a=(a*a)%mod;
            b>>=1;
        }
        return res;
    }
    void solve(){
        cin>>n;
        if(n==0||n==1) cout<<0<<'\n';
        else if(n==2) cout<<1<<'\n';
        else cout<<(n%mod)*((n-1)%mod)%mod*ksm(2,n-3)%mod;
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[C-_Wannafly_6 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/37/C
[6b6a311ffd974ffea068ef9f9f612fbe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/aad7e361df744a9faf63e99b1eca7855.png
[e65b5f35cb0e4589b92c3cfbc80f8001.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8b1bd0da2b5346ca9fdac9ee5a157e92.png
[07eb184940c703ac2904d1ab54291de7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8578146aa107437a992142f8ca5980be.png
[f2a66d9a3f2cb8b40db7dd4b012079b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/05ea8bf088aa4f5bb527266e7d7940c9.png
[3f128e405caacc8270f2d3d58417c67c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/32ed52616a004dcdbef51eb34b375ae9.png