题目大意

给你一个区间\([l,r]\)，求这个区间内每个整数的十进制上从高位到低位的逆序对个数之和。

思考历程

一开始就知道这是个数位DP……

结果一直都没有调出来，心态崩了……

正解

先讲讲我的SB做法。

先设\(f_i\)表示压着第\(i\)位（从低位到高位，从\(0\)开始）的贡献。

于是转移就是这样：

计算第\(i\)位的贡献。这一位的贡献可能有点难计算，所以我预处理了一个\(h_{i,j,0/1}\)表示是否压着\(i\)位，\(0\)到\(i\)位对\(j\)的贡献（\(j\)是\(i\)位之后的某个在\([0,9]\)之间的数）。那么这个东西就是\(h_{i,a_i}\)

从\(i-1\)位转移过来，其中\(i-1\)位也被压着。显然是\(f_{i-1}\)。

从\(i-1\)位转移过来，其中\(i-1\)位不被压着。枚举这一位选择\(x\)，贡献就是\(\sum_{x=0}^{a_{i-1}-1}|x<j|*10^{i-1}+g_{i-2}+(i-1)*10^{i-2}x\)。\(g_i\)表示\(0\)位到\(i\)位任意选的方案数。这条式子可以化简，这里就不打出来了。

先考虑\(g\)怎么转移，显然是从前面转移过来并且加上这一位的贡献。

也就是\(g_i=10*g_{i-1}+\frac{(0+9)*10}{2}i*10^i\)

再考虑\(h\)的转移。

\(h_{i,j,0}=j*10^i+10*h_{i-1,j,0}\)

\(h_{i,j,1}\)的转移相对复杂一些。和\(f\)的转移有点类似。

记\(num\)为\(0\)到\(i-1\)位形成的十进制数，也就是整个数模\(10^i\)。

\(h_{i,j,1}=|a_i<j|*(num+1)+h_{i-1,j,1}+(\sum_{x=0}^{a_{i-1}-1}|x<j|*10^{i-1}+h_{i-2,j,0})\)

同样也可以化简一下。

化简后，很容易发现这样转移的时间复杂度是\(O(10n)\)的。

另外有个可能比较简单地比较高级的做法：

从高位到低位枚举一个\(i\)，表示\(i\)位压着上限，然后记下此时的贡献。

那么贡献有三种：

高于\(i\)的位和\(i\)的贡献。由于\(i\)是压着上限的，所以前面所有数字的出现次数可以用一个桶记录下来。

\(i\)位和低于\(i\)位的贡献。我们强制后面一位没有压着上限，因为后面那一位压着上限的方案数将会在后面计算到。枚举后面的一位，再后面的就可以随便选。

高于\(i\)位和低于\(i\)位的贡献。这个计算也跟上一个差不多。

然后就没了。

代码

这题是在是太恶心了……细节奇多无比……

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define mo 998244353#define LEN 500010#define ll long longchar str[LEN];int n,m,L[LEN],R[LEN];inline void read(int a[],int &n){    scanf("%s",str);    n=strlen(str);    for (int i=0;i
        
         =0?h[i-2][j][0]*a[i-1]:0)+tmp*pow10[i-1])%mo;        }    f[0]=0,f[1]=min(a[0]+1,a[1]);    for (int i=2;i<=n;++i)        f[i]=(h[i][a[i]][1]+f[i-1]+a[i-1]*g[i-2]+(i-1)*pow10[i-2]*((a[i-1]-1)*a[i-1]>>1))%mo;    return f[n];}int main(){    freopen("pair.in","r",stdin);    freopen("pair.out","w",stdout);    pow10[0]=1;    for (int i=1;i<=500001;++i)        pow10[i]=pow10[i-1]*10%mo;    int T,ty;    scanf("%d%d",&T,&ty);    while (T--){        read(L,n),read(R,m);        L[0]--;        for (int i=0;L[i]<0;++i)            L[i+1]--,L[i]+=10;        if (!L[n-1])            n--;        printf("%lld\n",(get(R,m)-get(L,n)+mo)%mo);    }    return 0;}