题解 P2518 【[HAOI2010]计数】
C3H5ClO
2019-06-12 14:22:31
~~总感觉题面很不清楚啊，看了题解才搞明白~~
搞了半天才发现，这不就是可重复元素排列的康托展开！0~9数字随便排，求一下有多少排列字典序比题目给的排列小。
先说普通的康托展开吧。其实运用了数位DP的思想。
例如，给你一个排列：２ ４ ５ ３ １，求字典序比它小的排列有几个。
先看第一位。当第一位小于2时后4位无论怎样都比原排列小。而小于2且未被使用的数只有1一个。因此答案加上1×4!。当第一位等于2时，后4位必须小于原排列后4位。此时将2标记为已使用，继续循环。
看第二位。第一位小于4的数去除已使用的2还有2个，因此答案加上2×3!。然后将4标记为已使用，继续处理第二位为4的情况。
以此类推，可算得原排列康托展开为1×4!+2×3!+2×2!+1×1!+0×0!=41
可重复元素排列的康托展开也用同样的方法处理。
先存储0~9中每个元素的个数。对于每一位，枚举所有小于原排列中当前位的数。然后计算其他未被使用的数的全排列加入答案。最后将原排列中当前位的元素的值的个数减一，继续循环。具体看代码。
算可重复元素全排列个数的方法其他几位dalao已经讲的很清楚了。
```cpp
#include<cstdio>
using namespace std;
#define ri register int
#define ll long long
ll ans,c[55][55];
int a[10],len,n[55],cnt;
ll multiqpl(int a[],int l)
{
ll res=1;
for(ri i=0;i<=9;i++)
{
res*=c[l][a[i]];
l-=a[i];
}
return res;
}
int main()
{
for(char ch=getchar();ch>='0'&&ch<='9';ch=getchar())a[n[++len]=ch-48]++;
c[0][0]=1;
for(ri i=1;i<=len;i++)
{
c[i][0]=c[i][i]=1;
for(ri j=1;j<i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1];
}
for(ri i=1;i<=len;i++)
{
cnt=0;
for(ri j=0;j<n[i];j++)
if(a[j])
{
a[j]--;//将j放到第i位上
ans+=multiqpl(a,len-i);
a[j]++;//将j拿走，换下一个
}
a[n[i]]--;
}
printf("%lld",ans);
}
```