P2518 [HAOI2010]计数

· · 题解

看到其它题解写的都是组合计数或者看不懂的数位dp，这里给出一种易懂的数位dp。

我们发现原问题就转化成了一个有重复元素全排列在全排列中的排名，于是考虑数位dp。

记录下每个数字出现的次数（0不必记录），进行数位dp时，能取就取，并且记录一个limit表示是否有最高位限制。

接下来分两种情况：

1、有最高位限制：继续dp。

2、没有最高位限制：我们发现，此时后面的数无论怎么排，构成的排列也一定比读入的排列小，所以我们可以直接计算后面的全排列并计入答案。

关键在于如何求全排列，有重复元素全排列个数是：\dfrac {\left( \sum a_{i}\right) !}{\Pi \left( a_{i}\right) !}

但是，分子可能会很大，我们不能直接用阶乘去算，这该怎么办呢？

我们可以用质因数分解的办法把分子分解的每一项质因子的系数存好，分母各项直接去除就可以了。

具体细节详见代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<utility>
#include<algorithm>
#include<iostream>
using namespace std;
#define res register int
#define ll long long
const ll prime[16]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}; //质数表，只要打到这里就够了。
char s[51];
int tong[16],num[10],len1,sum,a[51],len; //tong数组记录质因子出现次数
inline void ins(int x) { //乘法
    for(res i=1;i<=15;++i)
      while(!(x%prime[i])&&x) ++tong[i],x/=prime[i];
}
inline void del(int x) { //除法
    for(res i=1;i<=15;++i)
      while(!(x%prime[i])&&x) --tong[i],x/=prime[i];
}
inline ll query(int len,int s) {
    if(len<sum-s) return 0; //这里有个细节：如果剩下的非0个数仍大于需要填的数，此时不可能达到排列，直接返回0。
    memset(tong,0,sizeof(tong));
    for(res i=1;i<=len;++i) ins(i);
    for(res i=1;i<=9;len-=num[i++]) for(res j=1;j<=num[i];++j) del(j);
    for(res i=1;i<=len;++i) del(i); //剩下的len就是0的个数，也需要除
    ll tot=1;
    for(res i=1;i<=15;++i)
      for(res j=1;j<=tong[i];++j) tot*=prime[i]; //最后把每一项乘起来就能得到答案了。
    return tot;
}
ll dfs(int len,int s,bool ff) {
    ll tot=0;
    if(!len) return s==sum;
    if(!ff) return query(len,s); //没有限制直接求答案
    int end=ff?a[len]:9;
    for(res i=0;i<=end;++i) {
        if(!num[i]&&i) continue;
        --num[i],tot+=dfs(len-1,s+(i>0),ff&&i==end),++num[i]; //回溯
    }
    return tot;
}
int main()
{
    cin.sync_with_stdio(false); //sync加速（貌似这题没什么用）
    cin>>s,len1=strlen(s);
    for(res i=len1-1;~i;--i) {
        if(s[i]^48) ++num[s[i]-48],++sum; //sum表示非0数个数，num记录每个数出现次数。
        a[++len]=s[i]-48;
    }
    printf("%d\n",dfs(len,0,true)-1);
    return 0;
}