【UOJ241】【UR#16】破坏发射台

一题rk4虐场真愉快

首先奇数的情况是不需要考虑相对的,我们可以写出一个显而易见的dp

我们称第一个点的颜色为\(1\),令

\(dp[i][0]\)表示当前格子颜色不为\(1\)的方案数

\(dp[i][1]\)表示当前格子颜色为\(1\)的方案数

那么\(dp[1][1]=m\),答案为\(dp[n][0]\)

转移很简单

对于偶数的情况,我们可以考虑每次决策相对的两个点的颜色

形象的说,就是将后半段环叠在前半段环的上面

就变成了一个\(2\times n\)的矩阵

那么我们称第一行第一个的颜色为\(1\),第二行第一个的颜色为\(2\),其他颜色为\(0\)

那么对于每一列有7种状态,转移一下即可

当然转移要用矩阵快速幂

说点什么

  Subscribe  
提醒