数(组)位(合)d(数)p(学) 经典题

题目描述

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

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

输入格式

只有1行，为1个整数n.

输出格式

只有整数，表示N之前出现的数的个数。

Inputs and Outputs examples

Inputs’ e.g. #1

Outputs’ e.g. #1

数据范围

n的长度不超过50，答案不超过$2^{63}-1$.

分析

这玩意为什么要被放到数位dp的试炼场里……

观察题意,我们可以做一个微小的联想－－把一个数中的一个0删除相当于把这个0挪到这个数的最前面.

那么题目也就转化成,统计一个数的全排列中比此数小的数的个数.

我们可以模仿数位dp中验证最大值限制时的做法,考虑用$num[i] \quad i \in [0,9]$来统计这个数中$0 - 9$的出现次数.

首先我们从最高位开始填数,设最高位填了数$j$,那么num[j]--.

然后我们从$0$开始填,其方案数为$\binom{n - 1}{num[0]}$

然后开始填$1$,这时候只有$n - 1 - num[0]$个位置了,方案数为$\binom{n - num[0] - 1}{num[1]}$

依次类推,我们根据乘法原理可以得到答案为:

$$\prod_{i=0}^9 \binom{n - 1 - \sum_{j=0}^i num_j}{num_i}$$

具体细节可以康康代码.

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
#define type_T long long
const int MAXN = 1e3 + 10;
type_T YH[MAXN][MAXN];
int num[10],val[100],cnt;
/* functions */
inline void Combination(){
    memset(YH,0ll,sizeof(YH));
    YH[1][0] = YH[1][1] = 1ll;
    FOR(i,2,1005,1){
        YH[i][0] = 1ll;
        FOR(j,1,i,1) YH[i][j] = YH[i-1][j] + YH[i-1][j-1];
    }
}
inline type_T calcans(){
    type_T ans = 1;
    int m = cnt;
    FOR(i,0,9,1) {if(num[i]) {ans *= YH[m][num[i]]; m -= num[i];}}
    return ans;
}
int main(int argc,char *argv[]){
    Combination();
    char s = getchar();
    while(true){if(!isdigit(s)) break; val[++cnt] = s - 48; num[val[cnt]]++; s = getchar();}
    int n = cnt; type_T ans = 0;
    FOR(i,1,n,1){
        cnt--;
        FOR(j,0,val[i] - 1,1)
            if(num[j]){num[j]--; ans += calcans(); num[j]++;}
        num[val[i]]--;
    }
    printf("%lld\n",ans);
    return 0;
}

LuoguP2518「HAOI2010」题解