Numbers from a Digit Multiset
National Olympiad — National round
Submission name: num.cpp
Problem summary
Delete any subset of digits of A and rearrange the retained digits. Count distinct nonempty numbers obtainable without leading zeros; the single digit 0 is allowed. Return the count modulo 1,800,000,007.
Input
A in decimal.
Output
The count modulo 1,800,000,007.
Constraints
0 ≤ A ≤ 10¹⁰⁰.
Worked example
An independently prepared example for this explanation.
Input
12
Output
4
Solution analysis
- Count strings from the available digit counts with an insertion DP: inserting j copies of a new digit into a length-l string has C(l+j,j) choices.
- Sum all lengths, including the empty string. If zero exists, repeat with one zero removed: these strings represent all zero-prefixed strings after deleting their first zero. Subtract that count, with the empty-string and single-zero exceptions cancelling. Without zero, subtract only the empty string.
Why it works
Insertion positions uniquely identify every string of the processed digit types. Strings of length≥2 beginning with zero are invalid and correspond bijectively to nonempty suffixes from the reduced multiset. This gives the stated subtraction.
Watch out. The modulus need not be prime; Pascal addition avoids modular division.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Insertion positions uniquely identify every string of the processed digit types. Strings
// of length≥2 beginning with zero are invalid and correspond bijectively to nonempty suffixes from the
// reduced multiset.
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
using namespace std;
const long long MOD=1800000007;
long long C[103][103];
long long countWays(vector<int>c){
vector<long long>dp(103);
dp[0]=1;
int used=0;
for(int z:c){
vector<long long>nd(103);
for(int l=0;l<=used;l++){
for(int j=0;j<=z;j++){
nd[l+j]=(nd[l+j]+dp[l]*C[l+j][j])%MOD;
}
}
used+=z;
dp.swap(nd);
}
long long ans=0;
for(auto x:dp){
ans=(ans+x)%MOD;
}
return ans;
}
int main(){
string s;
cin>>s;
vector<int>c(10);
for(char x:s){
c[x-'0']++;
}
for(int i=0;i<103;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++){
C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
}
}
long long ans=countWays(c);
if(c[0]){
--c[0];
ans-=countWays(c);
}
else{
--ans;
}
cout<<(ans+MOD)%MOD<<'\n';
}