Day6
今天打了一场模拟赛
T1：
推出性质：每一个色块之间间隔大于 \(k\) , 每一个色块中必然存在一个等于 \(k\) 的色段
然后, 不会用, 想到计数问题一般直接推出式子或者 \(dp\) , 看到这里的 \(n \le 10^{18}\) , 果断选择放弃 \(dp\) , 推半天组合数ing
最后打一个 \(n^2\) 的吧, 推一下 \(dp\) , 没有推出来, 放弃了
正解：
\(f[i][j][0/1]\) 表示考虑到前 \(i\) 个, 最近的一个色块长度为 \(j (j \le k + 1)\) , 色块内是否有大小大于 \(k\) 的色段
\(f[i][j][0] = f[i - 1][j - 1][0] (2 \le j \le k)\)
\(f[i][j][1] = f[i - 1][j - 1][1] (2 \le j \le k)\)
\(f[i][1][0] = \sum_{j = 1}^{k + 1} [j != k] f[i - 1][j][0]\)
\(f[i][1][1] = \sum_{j = 1}^{k + 1} f[i - 1][j][0] + f[i - 1][k][1]\)
\(f[i][k + 1][0] = f[i - 1][k][1] + f[i - 1][k + 1][0]\)