越来越懒了，现在连 LaTeX 都懒得写了。
题意
https://www.luogu.com.cn/paste/t9tg8cs6 这个的 T1。
解析
首先考虑 O(n) 怎么做。
假设每个位置都需要被涂过一边颜色，那么这个不和谐序列合法的充要条件就是：
- 存在一个长度为 k-1 的连续 0，因为最后一次涂的颜色一定会让长度为 k 的连续段拥有相同颜色
- 不存在长度为 k 的连续 0，因为一次涂的颜色长度只能是 k
充分性大概是因为有 n 中颜色，足够多。
所以可以令 f(i) 表示考虑前 i，目前还没有出现过一段长度为 k-1 的连续 0，且第 i 位为 1 的方案数，同理令 g(i) 表示出现过一段长度为 k-1 的连续 0 的方案数。通过前缀和优化 dp 可以做到 O(n)。
但是存在没有涂色的部分，这就允许了存在长度大于等于 k 的连续 0。我们可以拆分成多段每个位置都涂过一边颜色的，就再次套用上面的求法即可，即，出现长度为 k-1 的连续 0，就从 f 转移到 g，出现长度大于等于 k 的连续 0 就从 g 转移到 f。仍然可以做到 O(n)：
std::vector<mint> f(mq + 1), g(mq + 1);
std::vector<mint> sf(mq + 2), sg(mq + 2);
f[0] = 1;
g[0] = 1;
sf[1] = 1;
sg[1] = 1;
for (int i = 1; i <= mq; i++) {
if (0 < i - k) f[i] += sg[i - k];
f[i] += sf[i] - sf[std::max(0, i - k + 1)];
if (i - k >= 0) g[i] += f[i - k];
g[i] += sg[i] - sg[std::max(1, i - k)];
sf[i + 1] = sf[i] + f[i];
sg[i + 1] = sg[i] + g[i];
}
for (auto i : q) {
mint ans = g[i] + sg[std::max(1ll, i - k)] - sg[1];
std::cout << ans.val() << " ";
}继续优化，由于这些转移都是线性的，所以考虑矩阵快速幂。首先这些 sf 和 sg 都可以压缩掉。转移矩阵大小是 2(k+2) x 2(k+2) 的，直接矩阵快速幂复杂度是 O(k^3logV) 由于有多次询问，无法通过，但是由于一个方阵乘以一个列向量复杂度是 O(n^2) 的，所以预处理转移矩阵的 2^w 次方，二进制拆分，乘到列向量上，复杂度就是 O(k^2logV) 可以通过。
int main()
{
set_io("painting");
int t, k;
std::cin >> t >> k;
std::array<mint, 53> f, g;
f[1] = 1;
g[1] = 1;
for (int i = 1; i < 52; i++) {
f[i + 1] = f[i];
g[i + 1] = g[i];
if (i - k > 0) f[i + 1] += g[i - k];
f[i + 1] += f[i] - f[std::max(0, i - k + 1)];
if (i - k >= 0) g[i + 1] += f[i - k + 1] - f[i - k];
g[i + 1] += g[i] - g[std::max(1, i - k)];
}
Matrix<mint, 104, 1> init;
for (int i = 0; i < 52; i++) {
init[i * 2][0] = f[i + 1];
init[i * 2 + 1][0] = g[i + 1];
}
Matrix<mint, 104, 104> trans;
for (int i = 0; i < 51; i++) {
trans[i * 2][(i + 1) * 2] += 1;
trans[i * 2 + 1][(i + 1) * 2 + 1] += 1;
}
{
int i = 51;
trans[i * 2][i * 2] += 1;
trans[i * 2 + 1][i * 2 + 1] += 1;
trans[i * 2][(i - k) * 2 + 1] += 1;
trans[i * 2][i * 2] += 1;
trans[i * 2][(i - k + 1) * 2] -= 1;
trans[i * 2 + 1][(i - k + 1) * 2] += 1;
trans[i * 2 + 1][(i - k) * 2] -= 1;
trans[i * 2 + 1][i * 2 + 1] += 1;
trans[i * 2 + 1][(i - k) * 2 + 1] -= 1;
}
std::vector<Matrix<mint, 104, 104>> trans_pow(64);
trans_pow[0] = trans;
for (int i = 1; i < 64; i++) trans_pow[i] = trans_pow[i - 1] * trans_pow[i - 1];
for (int i = 0; i < t; i++) {
i64 n;
std::cin >> n;
if (n <= 51) {
std::cout << (g[n + 1] - g[n] + g[std::max(1ll, n - k)] - g[1]).val() << " ";
} else {
u64 d = n - 51;
auto res = init;
for (int i = 0; i < 64; i++) {
if ((d >> i) & 1) {
res = trans_pow[i] * res;
}
}
std::cout << (res[51 * 2 + 1][0] - res[50 * 2 + 1][0] + res[(50 - k) * 2 + 1][0] - g[1]).val() << " ";
}
}
std::cout << std::endl;
}