Gym-102040B Counting Inversion

Gym-102040B

题意：对于每一个十进制数，我们定义逆序对数。如果一个数位在另一个数位之后，并且比前面那个数位大，则逆序对数加1。现在求[L,R]中，每一个数字的逆序对数之和。

题解：dp [i] [j] 表示考虑到第i位，并且填数字j时，当前数位和接下来要填写的数位形成的逆序对数是多少。显然，除了递归处理的部分，我们还应该加上第i位填j的贡献。这个贡献直接算是不好算的，由于还受到limit的限制，所以很自然的要是用数位dp去计数。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 20;
const int M = 10;

int st[N], tol;

LL f1[N][M][2], f2[N][M][2];

LL preSum[N][2];

LL l, r;

LL dfs2(int dep, int x, int flag){
    if(dep==0)return 0;
    if(~f2[dep][x][flag])return f2[dep][x][flag];

    int up=flag?st[dep]:9;
    LL& res=f2[dep][x][flag];

    res=0;
    for(int i=0;i<=up;++i){
        res+=dfs2(dep-1,x,flag&&i==up);

        if(i>x){
            res+=preSum[dep][flag&&i==up];
        }
    }

    return res;
}

LL dfs1(int dep, int head, int flag){
    if(dep==0)return 0;

    if(~f1[dep][head][flag])return f1[dep][head][flag];

    int up=flag?st[dep]:9;
    LL& res=f1[dep][head][flag];

    res=0;
    for(int i=0;i<=up;++i){
        res+=dfs1(dep-1,head&&i==0,flag&&i==up);
        if(!head||i!=0){
            res+=dfs2(dep-1,i,flag&&i==up);
        }
    }

    return res;
}

LL cal(LL x){
    memset(f1,-1,sizeof f1);
    memset(f2,-1,sizeof f2);
    memset(preSum,0,sizeof preSum);
    tol=0;

    while(x>0){
        st[++tol]=x%10;
        x/=10;
    }

    LL s1=1, s2=0, pw=1;
    for(int i=1;i<=tol;++i){
        preSum[i][0]=s1;
        preSum[i][1]=s2+1;
        s1*=10;
        s2+=pw*st[i];
        pw*=10;
    }

    return dfs1(tol,1,1);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int kase=1;

    int _;cin>>_;
    while(_--){
        cin>>l>>r;
        cout<<"Case "<<kase++<<": "<<cal(r)-cal(l-1)<<endl;
    }
    return 0;
}