Problem

你有一组非零数字（不一定唯一），你可以在其中插入任意个 0，这样就可以产生无限个数。比如说给定 {1,2}, 那么可以生成数字 12,21,102,120,201,210,1002,1020, 等等。

现在给定一个数，问在这个数之前有多少个数。（注意这个数不会有前导 0）.

范围：n 长度不超过 50。答案不超过 $2^{63}-1$

Solution

题解由 @noob 提供。
洛谷题解可见。地址：https://www.luogu.org/blog/CSGO/solution-p2518

由于 0 置于最前面代表前导零，则求所有比数字 n 小的排列即可。

则首先枚举最大位数。
然后枚举最高位的数字，接着算方案数。
然后最大位的数字固定为原位数字上限，位数 -1，继续枚举最高位，算方案数。
所有方案数相加即可。

已知位数 m 和每个数字 i(0~9)的个数 ai。怎么求组合方案数？
假设我们先把 0 固定。则方案数为 $C(m,a_0)$。然后再把 1 固定，则方案数为 $C(m-a_0,a_1)$。以此类推。
按照乘法原理，最终答案是 $C(m,a_0)C(m-a_0,a_1)C(m-a_0-a_1,a_2)...$。若 $a_i=0$，则不参与讨论。

Code

// Code by ajcxsu
// Sol by @Ju_Xing_Fang_Kuai

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1010;
long long f[N][N];

ll C(int i,int j) {
    if(i==j || j==0) return 1;
    if(f[i][j]) return f[i][j];
    f[i][j]=C(i-1,j)+C(i-1,j-1);
    return f[i][j];
}

int n;
int v[100],a[20];

ll deal() {
    int m=n;
    ll ret=1;
    for(int i=0;i<=9;i++)
        if(a[i]) ret*=C(m,a[i]), m-=a[i];
    return ret;
}

int main() {
    char ch;
    while(cin>>ch)
        if(isdigit(ch)) v[n++]=ch-'0', a[v[n-1]]++;
    int nn=n;
    ll ans=0;
    for(int i=0;i<nn;i++) {
        n--;
        for(int j=0;j<v[i];j++)
            if(a[j]) { a[j]--; ans+=deal(); a[j]++; }
        a[v[i]]--;
    }
    cout<<ans<<endl;
    
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol_luogu_2518.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆