设状态为 $dp_{i,j,k}$ 分别表示填了 $i$ 位，当前内层 $dp$ 状态为 $j$，匹配 $NOI$ 的状态为 $k$ 的方案数。你应当对于固定的 $i,j$ 计算出填 $N、O、I$ 对应的新 $j$。若每次枚举 $i,j,k$ 都重新计算，你就会喜提常数 $\times 3$。

见 大常数 和 小常数 提交记录。