ICPC Asia Regional Tsukuba 2015 E - Bringing Order to Disorder

問題文 : Bringing Order to Disorder

概要

leading-zero を含む 桁の数に次の順序 を導入する。

1. 数 の各桁の和を とあらわすとき, ならば
2. 数 の各桁に 1 を足したものを掛け合わせたものを とあらわすとき, かつ のとき
3. かつ かつ のとき,

このとき, leading-zero を含んだ 桁の数全体を考えるときに, より小さな数がいくつあるか数えよ。

他のチームと違う解で解いて, AOJ では 0.00 s で通ったので解法を紹介します。

解法

1 番目の比較条件に関しては, の各桁の数の和を求めて(これを とする), [S - 1] :] 桁の数で各桁の和が 以下となるもの という DP の計算を行えばこの条件で より小さい数の個数が求まります。
2 番目の条件に関しては, が等しくて が等しい数は, と のように並びだけが違うものを無視すると, 14 桁の時でも最大で 50000 個もないことが簡単な DP で確かめられます。よって, が同じ数の集合を全探索して, 重複順列を求めればいいです。

コード

#include <bits/stdc++.h>

using namespace std;

typedef long long Int;

int N, S;
char s[16], s2[16];

Int memo1[16][14 * 9];

Int func1(int N, int S)
{
	if (S < 0) return (0);
	if (N == 0) return (1);
	if (~memo1[N][S]) return (memo1[N][S]);
	
	Int ans = 0;
	for (int i = 0; i <= 9; i++){
		ans += func1(N - 1, S - i);
	}
	
	return (memo1[N][S] = ans);
}

Int pos;
Int fact[15], ten[15];

Int calcComb(int *a)
{
	Int den = 1, sum = 0;
	
	for (int i = 0; i <= 9; i++){
		sum += a[i]; den *= fact[a[i]];
	}
	
	return (fact[sum] / den);
}

Int prod;

void func2(int n, int sum, int l, Int tmp = 0, Int tprod = 1)
{
	if (sum < 0) return;
	if (n * l < sum) return;
	
	if (n == 0){
		if (sum == 0 && tprod < prod){
			int a[10] = {0};
			for (int i = 0; i < N; i++){
				a[tmp % 10]++; tmp /= 10;
			}
			pos += calcComb(a);
		}
		if (sum == 0 && tprod == prod){
			int a[10] = {0};
			for (int i = 0; i < N; i++){
				a[tmp % 10]++; tmp /= 10;
			}
			for (int i = 0; i < N; i++){
				for (int j = 0; j < s[i] - '0'; j++){
					if (a[j]){
						a[j]--;
						pos += calcComb(a);
						a[j]++;
					}
				}
				if (a[s[i] - '0']) a[s[i] - '0']--;
				else break;
			}
		}
		return;
	}
	
	Int orig = tmp;
	for (int i = min(l, sum); i >= 0; i--){
		tmp = tmp + i * ten[N - n];
		func2(n - 1, sum - i, i, tmp, tprod * (i + 1));
		tmp = orig;
	}
}

int main()
{	
	fact[0] = ten[0] = 1;
	for (int i = 1; i <= 14; i++){
		fact[i] = i * fact[i - 1];
		ten[i] = 10 * ten[i - 1];
	}
	
	scanf("%s", s);
	prod = 1;
	for (int i = 0; s[i]; i++){
		S += s[i] - '0';
		prod *= (s[i] - '0' + 1);
		N++;
	}
	
	memset(memo1, -1, sizeof(memo1));
	pos = func1(N, S - 1);
	
	func2(N, S, 9);
	
	printf("%lld\n", pos);
	
	return (0);
}