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]\)