[SNCPC2019] Digit Mode 题解

· · 题解

模拟赛 T3，场切了。赛后得知原题后翻了一下题解区，发现居然没有和我一样的做法，于是写一篇题解造福后人。

下文记整数 n 的“长度”（即十进制下的位数）为 \mathrm{len}(n)。

考虑数位 DP，从高位到低位枚举。记录三个信息，分别为当前处理到的位置 x（这里规定下标从 0 开始，即最高位所对应的 x=0，次高位的 x=1，以此类推）、目前确定的所有位是不是全部为 0（即处于“前导零”的阶段），以及后面的位是否可以随便取（例如上限为 9999，目前确定的最高的两位是 98，那么后面两位就可以取任意数）。使用 dfs 的写法，在 dfs 的同时动态维护一个数组 c(|c|=10)，表示每个数字在前面分别出现了多少次。

首先特判边界情况，对于已经确定所有位的情况（即当前的 x=\mathrm{len}(n)，前面的 0\sim \mathrm{len}(n)-1 位全部确定完了），直接暴力算出当前的值并加上。

对于后面不能任意取的情况，直接按照常规数位 DP 方法继续递归下去就行了；对于后面可以可以任意取的情况，此时需要一点组合数学方面的知识。枚举最终出现次数最多的最大数 i 以及其出现次数 j(\max\{c_i,1\}\le j\le c_i+\mathrm{len}(n)-x)，接着处理出其他所有数字 d(d\ne i) 最多新增的出现次数（即不考虑之前确定的 c_d 次）r_d=j-c_d-[d>i]，就变成了以下的问题：有若干种数字，数字 d 最多取 r_d 个，要求取正好 s 个数字（后面总共要填 (\mathrm{len}(n)-x) 个数字，除去 i 则总共要填 (\mathrm{len}(n)-x-j+c_i) 个），问有多少种不同的数字排列（\{1,1,2\} 和 \{2,1,1\} 算不同的选法，即可重集排列）。

想要求解上面这个问题，首先在所有数字 d 选的个数 w_d 都确定的情况下，根据可重集排列数公式，答案就是 \dfrac{(\mathrm{len}(n)-x)!}{\prod\limits_{d=0}^9w_d!}（这里对于 d=i 有 w_d=j-c_i，否则有 0\le w_d\le r_d）。回到原问题，在给定 w_d(d\ne i) 取值范围的情况下，这个问题可以 DP 求解：设 f_{d,p} 表示考虑了前 d 种数字，已经选了 p 个数字的答案（这里先不乘上 (\mathrm{len}(n)-x)!），有转移 f_{d,p}\leftarrow f_{d-1,p-w_d}\cdot\frac{1}{w_d!}，这里的 w_d 需要你在可行的范围内暴力枚举。最后记得将答案乘上 (\mathrm{len}(n)-x)!；你也可以为了方便处理，把需要选 (j-c_i) 个的数字 i 单独处理（这样对于其他 d\ne i 只需要存储一个 w_d 的上界，即 r_d），即在 DP 过程中不考虑 i 的情况，只是最后需要将答案乘上 \dfrac{(\mathrm{len}(n)-x)!}{(j-c_i)!} 而不是 (\mathrm{len}(n)-x)!。

这道题似乎就做完了。但是有个很恶心的点，就是前导 0。上面的计算方法可能会导致把带有前导 0 的数的答案算错（即可能把 m(001) 算成 0，因为在考虑前导 0 的情况下 0 比 1 多，然而事实上 m(001)=m(1)=1）。对于这种情况，只要考虑如果确定的所有位都是 0，即使当前这一位和后面的数字是任意取，也要枚举清楚这一位到底要取哪一个数字，然后再递归下去，用上面的方法求解即可。

实测极限数据不超过 0.4s，可以通过此题。还是没搞清楚上面是怎么做的，可以参考代码注释。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=1e9+7;
static int f[52],d[52];
int n,r,c[10]; string s;
inline void chadd(int &x,int y){
  if((x+=y)>=p)x-=p;
}
inline int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)(r*=a)%=p;
    (a*=a)%=p,b>>=1;
  }
  return r;
}
inline int bf(){
  int x=0,d=0;
  for(int i=0;i<10;i++)
    if(c[i]>=x)x=c[i],d=i;
  return d;
} // 暴力求当前的值
inline int get(vector<int> &c,int s){
  if(s<0)return 0;
  vector<int> f(s+1); f[0]=1;
  for(int i:c)if(i){
    vector<int> g(s+1);
    for(int j=0;j<=s;j++)
      if(f[j])for(int k=0;k<=i&&j+k<=s;k++)
        chadd(g[j+k],f[j]*d[k]%p);
    f=g;
  } // 进行上述的 DP 转移，c[i] 是数字 i 取的个数上限
  return f[s];
}
void dfs(int x,bool l,bool b){
// 分别表示：当前位置，目前确定的是否全是 0，从这一位开始能不能随便取
  if(x==n)return chadd(r,l?0:bf()); // 暴力求
  if(!b){
    if(l){
      for(int i=0;i<10;i++){
        if(i)c[i]++;
        dfs(x+1,!i,false);
        if(i)c[i]--;
      } // 有前导 0，继续递归下去
    }
    else{
      for(int i=1;i<10;i++)
        for(int j=max(c[i],1ll);j<=c[i]+n-x;j++){
          vector<int> w;
          for(int k=0;k<i;k++)
            w.emplace_back(j-c[k]);
          for(int k=i+1;k<10;k++)
            w.emplace_back(j-c[k]-1);
          // 求每个数字取的个数的上限
          bool b=true;
          for(int i:w)if(i<0){b=false; break;}
          if(b)chadd(r,f[n-x]*d[j-c[i]]%p*get(w,n-x-j+c[i])%p*i%p);
        } // 枚举 i,j 进行求解 
    }
    return;
  }
  for(int i=s[x]-48;~i;i--){
    if(i||!l)c[i]++;
    dfs(x+1,l&&!i,i==s[x]-48);
    if(i||!l)c[i]--;
  } // 常规的数位 DP
}
main(){
  ios::sync_with_stdio(false);
  for(int i=f[0]=d[0]=1;i<=51;i++)
    d[i]=qpow(f[i]=f[i-1]*i%p,p-2);
    // 预处理阶乘及其逆元
  int t; cin>>t;
  while(t--){
    cin>>s,n=s.length(),r=0;
    memset(c,0,sizeof(c));
    dfs(0,true,true),cout<<r<<'\n';
  }
  return 0;
}