以下 \(N\) を文字列の長さとします。

解法 \(1\) ( \(N \leq 2 \times 10^5\) )

\(DP\)[何文字目まで決定したか] [ NPCAPC を何文字目まで含んでいるか][npcapcを何文字目まで含んでいるか] の \((N+1) \times 7 \times 7\) のDPを考え、以下のような遷移で答えを求めることができます。

\(DP[i][j][k]= \begin{cases} DP[i-1][j][k] \times 52(j=0,k=0) \\ DP[i-1][j][k] \times 51 + DP[i-1][j][k-1] (j=0,k \ne 0) \\ DP[i-1][j][k] \times 51 + DP[i-1][j-1][k] (k \ne 6,k = 0) \\ DP[i-1][j][k] \times 50 + DP[i-1][j][k-1] + DP[i-1][j-1][k] (j \ne 0,k \ne 0) \\ \end{cases}\)

解法 \(2\) ( \(N \leq 10^9\) )

\(M=49(=7 \times 7)\) として、\(M × M\) の正方行列 \(G\) を考えます。

( \(a =\) NPCAPC を含んでいる文字数, \(b= \) npcapcを含んでいる文字数とします, \(0 \leq a < 7,0 \leq b < 7\) )

解法 \(1\) の \(DP\) の遷移より、\(a \times 7+b\)から\((a+1) \times 7+b , a \times 7+(b+1)\)に辺をつなげて、始点が \(0\) で終点が \(48\) の長さが \(N\) のパス数が答えだとわかります。

よって、\(G[a \times 7+b][(a+1) \times 7+b]=1,G[a \times 7+b][a\times 7+b+1]=1\) とし、それ以外を \(0\) とした \(G\) を \(N\) 回累乗した \(G^{N}[0][48]\) が答えだとわかります。

計算量は \(O(M^3 \log N) \)であるため、十分に間に合います。

本解法

解法 \(2\) より、正方行列 \(G\) を \(N\) 回累乗した \(G[0][48]\) が答えですが、 \(O(TN^3 \log M)\) だと間に合いません。

前提として、 \(N\) 次正方行列 \(A\) は、ある \(N\) 次多項式 \(f(x)\) に対して \(f(A)=O\)( \(O\) は零行列) を満たします。なので、 \(A^k\)の \((i,j)\)成分は、 \(N\) 次漸化式を持ちます。なので、 \(A^0\) から \(A^{2N}\) を計算してそこから母関数を復元できます。 また、復元方法は、 \(F(x) = A(x)/B(x) (deg(A) < N,deg(B) \le N,B\) の定数項は \(1\) ) であることが分かっていて、\(f(x) = F(x) \bmod x^{2N}\) が与えられているとします。(つまり、 \(F(x)\) の \(x^0,x^1,...,x^{2N-1}\) の係数が分かります)

このとき、 \(F(x)B(x) = A(x) \rightarrow f(x)B(x) = A(x) \bmod x^{2N}\) となって \(2N\) 本の方程式が立ちます。なので、 掃き出し法を用いて \(A,B\) の係数の分からない個数 \(2N\) 個を全て特定出来ます。

上の方法を用いて、まず \(G^0[0][48]\) から \(G^{2M-1}[0][48]\) の答えを求めます。 そして、 \(F(G)=O\) ( \(O\) は零行列) となる \(F\)を考え、\(A(G),B(G)\) を求め、Bostan Mori 法を用いることで、各クエリを \(O(M \log M \log N)\) で答えることが出来ます。 したがって、全体の計算量は\( O(T M \log M \log N)\) となり、十分に間に合います。