Bài "Factorial and powers of Two" trên codeforces

[Circuit]

Problem - 1646C - Codeforces

Phần code của em:

int Count_bits(ll n)
{
	int cnt = 0;
	while (n != 0)
	{
		if (n % 2 == 1) cnt++;

		n /= 2;
	}

	return cnt;
}

ll Decode(int n)
{
	int i = 0;
	ll sum = 0, factorial = 1;

	while (n != 0)
	{
		if (n % 2 == 1) sum += factorial;

		n /= 2;
		i++;
		factorial *= i;
	}

	return sum;
}

int main()
{
	int num;
	ll n;

	cin >> num;

	for (int i = 0; i < num; i++)
	{
		int Min = numeric_limits<int>::max();
		cin >> n;

		for (int j = 0; j < 32768; j++)
		{
			ll fac_sum = Decode(j);

			if (fac_sum > n) break;
			int bits = Count_bits(n - fac_sum);
			Min = min(bits + Count_bits(j), Min);
		}

		cout << Min << endl;
	}
	return 0;
}

Ý tưởng phần code trên là: n = (a1! + a2! + … + (a_k)!) + (2^(b1) + … + 2^(b_t)). Trong đó, a trong khoảng từ 0 -> 14. Như vậy số hạng tử cần để tạo ra n = số hạng tử giai thừa + số hạng mũ 2 = k + t. Ta có tổng cộng 2^15 - 1 trường hợp(tương đương dùng hoặc không dùng 0!, 1!, …, 14!). Em xét hết các trường hợp i: 0 -> 2^15 -1 rồi:

Tính k dựa trên số bit của i
Tính t dựa trên số bit của (n - (a1! + a2! + … + (a_k)!))

Không hiểu sai gì nhưng hệ thống vẫn cho TLE. Trong khi bài cho 3 giây và em thấy code chỉ chạy trong khoảng O(10^8). : D. Em cảm ơn trước ạ.

[noname00 (HK boy)]

Đánh giá một chút, code của bạn chạy trong O(t * 2^{15} * 15 * \log n) \approx 2e9, không phải 1e8 như bạn thấy đâu.

Có vài phần tử 2^0 = 0! = 1!,\ 2^1 = 2!, bạn cẩn thận xét thừa.

Gợi ý nằm trong tag của bài, bài này dùng bitmask. Thay vì bạn backtrack, bạn hãy lưu lại trạng thái của j vào 1 mảng 32768 phần tử.

Bạn phải trả lời được câu hỏi

dp_factorize[m | i] = phụ thuộc dp_factorize[m] như thế nào?