[AtCoder] [經典競程 90 題] 005 - Restricted Digits（★7）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_e
題目大意:
給定 $c_i$ 代表可以用的數字種類，問在只用 $c_i$ 的情況下有多少 $N$ 位數是 $B$ 的倍數。

---

原本想暴力數位統計 DP 下去 ，但發現 $N$ 太大不能做，想了很久之後最後跑去看解答，我就爛= =
解答感覺也是一個很套路的東西，因為我們只要求 $N$ 位數而不是特定少於某個 $K$ 的數字，所以其實可以直接對 $N$ 倍增。初始狀態給的是 $1$ 位數的情況，那我們就可以倍增出 $2$ 位數的情況、$4$ 位數的情況、 $8$ 位數的情況...，對於 $N$ 位數，我們考慮它的二進位寫法，假設它是 $2^0 + 2^4 + 2^5$ 那我們就挑 $2^0$ 位數的情況、 $2^4$ 位數的情況、 $2^5$ 位數的情況來合併就好。
具體合併就是背包合併直接暴力枚舉高位跟低位分別模 $B$ 餘多少就好。

#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;
using llu = uint64_t;
constexpr int M = 3000 + 5;
constexpr int N = 64;
constexpr int MOD = 1'000'000'007;

static inline int add(int x, int y, int mod = MOD) {
	return x + y >= mod ? x + y - mod : x + y;
}
static inline void adde(int &x, int y, int mod = MOD) {
	x += y;
	if (x >= mod) x -= mod;
}
static inline int mul(int64_t x, int64_t y, int mod = MOD) {
	return static_cast<int>(x * y % mod);
}

int dp[N][M];
int ans[M], tmp[M];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	llu n; int b, k; cin >> n >> b >> k;
	for (int i = 0; i < k; ++i) {
		int c; cin >> c;
		dp[0][c % b]++;
	}

	bool initialized = false;
	if (n & 1) {
		for (int i = 0; i < b; ++i)
			ans[i] = dp[0][i];
		initialized = true;
	}
	
	int mul10 = 10;
	for (int i = 1; i < N; ++i) {
		for (int x = 0; x < b; ++x) {
			for (int y = 0; y < b; ++y) {
				adde(dp[i][add(x, mul(mul10, y, b), b)], mul(dp[i - 1][x], dp[i - 1][y]));
			}
		}

		mul10 = mul(mul10, mul10, b);
		
		if ((static_cast<llu>(1) << i) & n) {
			if (not initialized) {
				for (int x = 0; x < b; ++x)
					ans[x] = dp[i][x];
				initialized = true;
			} else {
				for (int x = 0; x < b; ++x) {
					for (int y = 0; y < b; ++y) {
						adde(tmp[add(x, mul(mul10, y, b), b)], mul(ans[y], dp[i][x]));
					}
				}
				copy_n(tmp, b, ans);
				memset(tmp, 0, sizeof(tmp));
			}
		}
	}
	cout << ans[0] << '\n';
	return 0;
}