[题解] LP2518 [HAOI2010] 计数

ajcxsu
ajcxsu 2018年02月26日
  • 21 次阅读

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://acxblog.site/archives/sol_luogu_2518.html
本文采用 CC BY-NC-SA 3.0 协议进行许可