越來越懶了，現在連 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;
}