[bzoj 3679] 数字之积

求[L,R)中满足0 <= 十进制各个数位之积 <= n的数的个数. (0<L<R<10^18, n≤10^9) 想用数位DP来做, 但是n≤10^9, 范围有点大......注意到, 所有可能的乘积的质因子皆为{2,3,5,7}的子集, 状态数一下小了很多. >_<

实现上至少有两种方法: - 2^a 3^b 5^c 7^d 用 (a,b,c,d) 表示. - 把所有形如 2^a 3^b 5^c 7^d 的数枚举出来, 用它在表中的下标表示.

方法二更简洁明了, 但我写的时候没想到. TAT

{% raw %}
typedef long long ll;

const int A = 30, B = 19, C = 13, D = 11, N = 19,
	t[][4] = {{},{},{1},{0,1},{2},{0,0,1},{1,1},{0,0,0,1},{3},{0,2}};

int a, b, c, d;
ll f[N][A][B][C][D][2] = {0,1};

inline ll get(ll f[A][B][C][D][2], int j, const int t[10])
{
	int _a = a - t[0], _b = b - t[1], _c = c - t[2], _d = d - t[3];
	return _a >= 0 && _b >= 0 && _c >= 0 && _d >= 0 ? f[_a][_b][_c][_d][j] : 0;
}

ll dp(int n, ll X)
{
	int x[19], l = 0;
	while (X) x[++l] = X % 10, X /= 10;
	reverse(x+1, x+1+l);
	
	ll y = 0, ans = 0;
	rep (i, 1, l+1)
	{
		y = y * 10 + x[i];
		ll pa = 1;
		for (a = 0; pa <= n; ++a, pa *= 2)
		{
			ll pb = pa;
			for (b = 0; pb <= n; ++b, pb *= 3)
			{
				ll pc = pb;
				for (c = 0; pc <= n; ++c, pc *= 5)
				{
					ll pd = pc;
					for (d = 0; pd <= n; ++d, pd *= 7)
					{
						ll* g = f[i][a][b][c][d];
						g[1] = x[i] ? get(f[i-1], 1, t[x[i]]) : 0;
						g[0] = i > 1 && pd < 10 && pd < y;
						rep (j, 1, 10) g[0] += get(f[i-1], 0, t[j]);
						rep (j, 1, x[i]) g[0] += get(f[i-1], 1, t[j]);
						ans += i == l ? g[0] : 0;
					}
				}
			}
		}
	}

	return ans;
}

int main()
{
	int n;
	ll L, R;
	scanf("%d%lld%lld", &n, &L, &R);
	printf("%lld\n", dp(n, R) - dp(n, L));
	return 0;
}
{% endraw %}