C - npcapc
题意
有 \(t\) 次询问，每次给出一个 \(n\)，问有多少个长度为 \(n\) 的包含大小写的字符串满足包含 \(\texttt{NPCAPC}\) 和 \(\texttt{npcapc}\) 两个子序列。\(t\le 5000,n \le 10^9\)。
思路
首先考虑直接计数，发现要去重，需要很复杂的容斥，很难做。
考虑 DP 然后矩阵快速幂优化。
设 \(f_{i,x,y}\) 表示考虑到字符串第 \(i\) 位，大写串已经匹配了 \(x\) 位，小写串已经匹配了 \(y\) 位，的方案数。枚举这一位填写什么字母即可转移。
考虑用矩阵快速幂优化 \(i\) 这一维。把 \(x,y\) 压成一维，初始矩阵是一个 \(49\times 1\) 的矩阵，其中 \(f_{0,0}=1\)。转移矩阵是一个 \(49 \times 49\) 的矩阵。因此求一个 \(n\) 时间复杂度是 \(m=49,O(m^3\log n)\) 的。
然而我们有 \(t\) 次询问。\(O(t m^3 \log n)\) 会爆。一个技巧是存下转移矩阵的 \(2^0,2^1 ,\dots 2^k\) 次幂。因为矩阵乘法满足结合律，我们要求的是转移矩阵的若干次幂乘上初始矩阵，因此可以从右边往左边算，初始矩阵是 \(m \times 1\) 的，这样时间复杂度就是 \(O(m^2 \log n)\) 的了。预处理 \(O(m^3 \log n)\)，询问 \(O(t m^2 \log n)\)。
标签：npcapc,log,49,矩阵,times,转移 From： https://www.cnblogs.com/liyixin0514/p/18475134