[PA2025] 乘数 / Mnożenie cyfr 题解

· · 题解

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

前一条性质是解决本题的关键，后一条性质可以简化做法：接下来的讨论中不考虑 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 分情况讨论：

注意特判 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;
}