一見複雑な構文解析を必要としそうに見えますが、よく考えるとかなり単純な構造をしています。発言の内容 \(s\) を整理すると、問題は次のように述べられます。

\(N\) 頂点 \(M\) 辺の有向グラフがある（\(a\) から \(b\) への辺があるところが「\(a\) は \(b\) に攻撃的」に対応するとする）。

頂点番号 \(g_0\) と、\(01\) 列 \(w = (w_1, \ldots, w_K)\) が与えられる。頂点の列 \((g_1, \ldots, g_K)\) があり、次の条件を満たしているという。

• \(w_i = 1\) のとき、\(g_{i-1} \leftarrow g_i\) の辺が存在する。

• \(w_i = 0\) のとき、\(g_{i-1} \leftarrow g_i\) の辺は存在しない。

\(g_K\) としてありうるものの個数を求めよ。

以下では、頂点 \(j\) から辺が出ている頂点の集合を \(S_j\) とします。

次のナイーブな DP を考えます。

• \(\mathrm{dp}(i, j) := \, g_i = j\) となる可能性があるか

\[ \mathrm{dp}(i, j) = \begin{cases} \displaystyle \bigvee_{j' \in S_j} \mathrm{dp}(i-1, j') & (w_i = 1) \\ \displaystyle \bigvee_{j' \notin S_j} \mathrm{dp}(i-1, j') & (w_i = 0) \\ \end{cases} \]

全体計算量は \(O(N^2 K)\) となり、部分点が得られます。

上の解法で時間がかかっているのは、\(j' \notin S_j\) についての遷移をしている部分です。\(j' \in S_j\) に関する遷移（辺が存在するところの遷移）だけで済ませられれば、計算量を \(O((N+M)K)\) に改善することができます。そのためには、or 演算は扱いづらいです。DP に \(01\) の情報だけでなく個数を持たせることにして、遷移を足し算にすることを考えましょう：

• \(\mathrm{dp2}(i, j) := \, g_i = j\) であるとしたとき、\(g_{i-1}\) としてありうるものの個数（補足：個数が \(1\) 以上なら \(g_i = j\) の可能性があるといえます）

\[ \mathrm{dp2}(i, j) = \begin{cases} \displaystyle \sum_{j' \in S_j} \mathbf{1}[\mathrm{dp2}(i-1, j') > 0] & (w_i = 1) \\ \displaystyle \sum_{j' \notin S_j} \mathbf{1}[\mathrm{dp2}(i-1, j') > 0] & (w_i = 0) \\ \end{cases} \]

\(w_i = 0\) の場合の遷移について、\(\displaystyle \sum_{j' \notin S_j} \mathbf{1}[\mathrm{dp2}(i-1, j') > 0] = \sum_{j' = 1}^N \mathbf{1}[\mathrm{dp2}(i-1, j') > 0] - \sum_{j' \in S_j} \mathbf{1}[\mathrm{dp2}(i-1, j') > 0]\) です。第 \(1\) 項は \(j\) によらないので前計算でき、第 \(2\) 項は \(j' \in S_j\) に関する遷移になったので、計算量は \(O((N+M)K)\) となり、満点が得られます。

発想としては、補グラフ上で DP する ABC212 E - Safety Journey に似ています。