読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

ICPC Asia Regional Tsukuba 2015 E - Bringing Order to Disorder

問題文 : Bringing Order to Disorder

概要

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

1. 数$x$ の各桁の和を $\text{sum}(x)$とあらわすとき, $\text{sum}(x) < \text{sum}(y)$ ならば $x \prec y$
2. 数$x$ の各桁に 1 を足したものを掛け合わせたものを $\text{prod}(x)$ とあらわすとき, $\text{sum}(x) = \text{sum}(y)$ かつ $\text{prod}(x) < \text{prod}(y)$ のとき $x \prec y$
3. $\text{sum}(x) = \text{sum}(y)$ かつ $\text{prod}(x) = \text{prod}(y)$ かつ $x < y$ のとき, $x \prec y$

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

$n \leqq 14$

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

解法

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

コード
#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);
}