BZOJ2425：[HAOI2010]计数——题解

https://www.lydsy.com/JudgeOnline/problem.php?id=2425

https://www.luogu.org/problemnew/show/P2518

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

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

题意看了半天终于看懂了。

我们从高位到低位枚举比当前位小的数，然后对于剩下的元素放在后面全排列即可。

可重元素全排列=元素个数！/每个元素个数！的乘积。

防止爆ll可以将分子分母分解后约分再计算。

（貌似本质上是一道很暴力有点思维的水题，不是数位dp）

#include<cstdio>

#include<iostream>

#include<vector>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

char s[N];

int n,sum,t[],p[N];

ll ans=;

int main(){

    cin>>s+;

    n=strlen(s+);

    for(int i=;i<=n;i++)t[s[i]-'']++,sum++;

    for(int i=;i<=n;i++){

    for(int j=;j<s[i]-'';j++){

        if(t[j]){

        memset(p,,sizeof(p));

        t[j]--;sum--;

        for(int k=;k<=;k++)

            for(int l=;l<=t[k];l++)

            p[l]++;

        ll tmp=;

        for(int k=;k<=sum;k++){

            tmp*=k;

            for(int l=;l<N;l++){

            while(p[l]&&tmp%l==){

                p[l]--;tmp/=l;

            }

            }

        }

        ans+=tmp;

        t[j]++;sum++;

        }

    }

    t[s[i]-'']--,sum--;

    }

    printf("%lld\n",ans);

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

秒客网

BZOJ2425：[HAOI2010]计数——题解

相关文章