222E

`2022.9.8 11:39 solution` 很简单的一道矩阵加速 dp，我们发现转移式非常好推，令 $f_{o,i}$ 表示第 $i$ 对核苷酸为 $o$ 的方案数，那么不难得到： $$f_{o,i}=\sum_{p=1}^{m} f_{o,i-1}\times [(p,o) \notin ......

这道题显然是一道 dp。转移方程式也很好推，我们记 $f_{i,j}$ 为前 $i$ 位且第 $i$ 位为 $j$ 的 DNA 序列数量。而对于输入的字符串，我们用 $vis_{i,j}=0$ 表示第 $i$ 个字母后面不能放第 $j$ 个字母。那么转移方程式即为： $$f_{i,j}= \sum ......

需要构造一个符合如下条件的字符串： 长度为 n，并且只包含字符 1∼m (n≤1e15,m≤52) 满足 K 个要求，第 i 个要求为 xi 后面不能是 yi 现在问你，有多少种字符串符合条件。 F[ i ][ j] += F[i -1] [lk ]* a[k][j] 用矩阵快速幂优化 即 F[1] ......