• \(A[i][k] := {}\)(この \(k\) において \(A_i'\) は母音か？)
• \(B[i][k] := \lnot A[i-1][k] \land A[i][k]\)

を計算しておくと，各 \(k\) について \(\sum_i B[i][k]\) を求める問題となります．
\(A, B\) はビット演算を利用して高速に計算することができます．\(\sum_i B[i][k]\) も同様にビット演算を活用して高速に計算できないでしょうか？

加算器を作る

\(A, B\) の各要素は \(1\) bit の幅に詰めこまれているので，個数をカウントするには，ビット演算で加算回路を作るのが良いでしょう．

すなわち，

const int lg = bit_width(N);
bool cnt[lg] = {};
void add(bool x) {
    for (bool& y : cnt) tie(x, y) = pair{x & y, x ^ y);
}

をビットごとに行います．

\(A, B\) をすべて保存しようとするとそれぞれ 1.87 GiB になるので，前計算ができないということに注意しながら bitset で実装すると，AC を取ることができます． 計算量は \(O(NK \log N / \text{word})\) 時間です．

実装例 (C++, 2228 ms)

さらなる高速化

加算器の幅は \(\log_2 N\) bit が最適なのでしょうか？
加算器の幅を \(w\) bit とすると，\(2^w - 1\) 要素ごとに \(wK\) 回の加算が必要になります．
計算量は \(O(wNK / \text{word} + wNK / 2^w)\) 時間となるので，\(w = \log_2 \text{word} + O(1)\) とすることで \(O(NK (\log_2 \text{word})/ \text{word} )\) 時間を達成できます．