【HAOI2010】计数

题面

https://www.luogu.org/problem/P2518

题解

按位数从大到小填数，每次考虑比当前数字小的情况，然后用可重集排列算方案加起来就可以了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 60
#define ri register int
#define LL unsigned long long
using namespace std;

string s;
int cnt[10];
LL ans=0;

LL C(int a,int b) {
  LL ret=1;
  for (ri i=b;i>=b-a+1;i--) ret*=i,ret/=(b-i+1);
  return ret;
}

LL pans(int a,int b) {
  LL ret=1;
  cnt[a]--;
  int sum=0;
  for (ri i=1;i<=9;i++) sum+=cnt[i];
  if (sum>b) return 0;
  for (ri i=1;i<=9;i++) ret*=C(cnt[i],b),b-=cnt[i];
  cnt[a]++;
  return ret;
}

int main() {
  cin>>s;
  for (ri i=0,l=s.size();i<l;i++) if (s[i]-'0') {
    cnt[s[i]-'0']++;
  }
  for (ri i=0,l=s.size()-1;i<=l;i++) if (s[i]-'0') {    
    for (ri j=0;j<s[i]-'0';j++) if (cnt[j] || j==0) ans+=pans(j,l-i);
    cnt[s[i]-'0']--;
  }
  cout<<ans<<endl;
  return 0;
}