自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:50:20，当前版本为作者最后更新于2024-08-23 19:16:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

模拟赛 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;
}