自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

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

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

以下是正文

对于这种题目，考虑函数 $f(x)$ 的性质：

• 乘法具有交换律，将 $x$ 的所有数位重排得到 $y$，则 $f(x)=f(y)$；
• $x$ 的数位中若出现 $0$ 则答案必然为 $0$。

前一条性质是解决本题的关键，后一条性质可以简化做法：接下来的讨论中不考虑 $f(x)=0$ 的情况，最后用 $n$ 减去其他情况的数量即可得到 $f(x)=0$ 的答案。

考虑针对前一条性质我们能做什么：定义两个数“处于同一个等价类”，当且仅当其中一个可以通过数位重排得到另一个数；则只需对于每一个等价类找一个代表元，这里选择其中字典序最小的：事实上等价类的个数并不多（经过测试，在题目给定的数据范围下共有 $48367$ 个），可以考虑使用拆分数相关知识进行证明（因为字典序最小，所以数位上的值是递增的），或直接打个表也可以得出该性质。

预处理出所有的代表元：只需在原有代表元的基础上，对于某个代表元，在末尾添加一个比原来的末尾更大的数位，即可生成一个新的代表元。

接下来的部分需要一个前置知识：多重集排列数。设多重集中每种元素的出现次数为 $n_1,n_2,\ldots,n_k$，集合大小为 $n$（满足 $n=\sum\limits_{i=1}^kn_i$），那么其全排列个数为 $\dfrac{n!}{\prod_{i=1}^kn_i!}$。

暴力枚举每个等价类，现在只需对于一个 $n$，求出某个等价类里面有多少个数 $\le n$。

记一个数的位数为 $\mathrm{len}(n)$。显然一个等价类内所有元素位数相等，于是对于代表元 $x$ 分情况讨论：

• $\mathrm{len}(x)>\mathrm{len}(n)$：答案为 $0$；
• $\mathrm{len}(x)<\mathrm{len}(n)$：$x$ 的所有数位重排方案均 $\le n$，答案为 $x$ 的数位构成的多重集排列数；
• $\mathrm{len}(x)=\mathrm{len}(n)$：进行数位 DP，从高位到低位考虑，每次取出 $x$ 中的一个数位填写：
  • 当前位上填的数字小于 $n$ 该位的数字：后面的数可以随便填，答案为余下的数位构成的多重集排列数；
  • 当前位上填的数字等于 $n$ 该位的数字：将该位忽略，递归对于更低的位解决原问题。

注意特判 $x=n$ 的情况。实现时为了提升效率，可以直接针对每一个代表元，支持加入 / 删除一个数位时快速计算排列数。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
static int fac[19];
inline int f(int x){
  while(x>9){
    int y=1;
    while(x)y*=x%10,x/=10;
    x=y;
  }
  return x;
} // 题目所述的 f(x)
struct number{
  int d,l,r; vector<int> c;
  number(int x):l(0),d(f(x)),c(10){
    while(x)l++,c[x%10]++,x/=10;
    r=fac[l]; for(int i:c)r/=fac[i];
  }
  inline void add(int x){r*=++l,r/=++c[x];}
  inline void del(int x){r*=c[x]--,r/=l--;}
};
// 结构体，维护一个等价类
// c 表示每个数字的出现次数
// l 表示元素的位数
// r 表示实时维护的当前数位构成的多重集排列数
main(){
  ios::sync_with_stdio(false);
  for(int i=fac[0]=1;i<=18;i++)
    fac[i]=fac[i-1]*i;
  vector<pair<int,int> > c;
  vector<number> s;
  for(int i=1;i<10;i++)
    c.emplace_back(i,i),s.emplace_back(i);
  for(int l=2;l<=18;l++){
    vector<pair<int,int> > d;
    for(auto [n,p]:c)
      for(int j=n%10;j<10;j++){
        int m=n*10+j;
        d.emplace_back(m,p*j);
        if(f(m))s.emplace_back(m);
      }
    c=d;
  } // 预处理所有代表元
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    string N=to_string(n);
    vector<int> c(10);
    for(number d:s){
      if(d.l>N.length())break;
      if(d.l<N.length()){c[d.d]+=d.r; continue;}
      bool f=true; // 是否可能出现 x=n
      for(int i=0;i<N.length();i++){
        if(N[i]==48){f=false; break;}
        for(int j=1;j<N[i]-48;j++)
          if(d.c[j])d.del(j),c[d.d]+=d.r,d.add(j);
        if(d.c[N[i]-48])d.del(N[i]-48);
        else{f=false; break;}
      } // 数位 DP 过程
      if(f)c[d.d]++;
    }
    c[0]=n-accumulate(c.begin(),c.end(),0ll);
    // 对于 0 的答案单独处理
    for(int i:c)cout<<i<<' ';
    cout<<'\n';
  }
  return 0;
}