この問題は「整数 \(n\) と、<または>からなる長さ \(n-1\) の文字列 \(s\) が与えられるので、良い順列の個数を求めよ。ただし、\(s\) のいくつかの区間は<<...>>または>>...<<の形になることのみが指定されているので、\(s\) としてありえるもの全てに対する答えの和を求めよ」という問題に帰着できます。(参考: 部分点解法の解説)

<<...>>または>>...<<となる区間(以下「不定区間」とします)が存在しない場合、包除原理を用いたDPを分割統治FFTで高速化することにより \(O(n(\log n)^2)\) でこの問題を解くことができます。 Nachiaさんのブログ に詳細が記載されており、以下ではこれを読んでいることを前提に解説を進めます。

>について包除原理を適用し、<または?からなる文字列について上記の解法を適用することを考えます。不定区間によりDPの遷移がどのように変わるか考えます。

<<...>> 型の区間について、 DPの遷移によって区間に入るときに、前何文字が<だったかによって値が \(-1\) 倍されるかされないかが変わりますが、ありえる<の数全てに対する和を求めればよいです。これは区間の左端からの距離の偶奇に応じて \(1\) または \(0\) を掛けることになります。掛ける数は(遷移元が区間の外側であるという条件のもとで)遷移元に依存しないため、畳み込みの後掛け算すればよいです。同様に、>>...<<型の場合は区間から出るときに畳み込みの前に掛け算すればよいです。

不定区間の内部での遷移は間にある文字が全て?であると考えればよいです。また、 <<...>>型区間から出るとき、>>...<<型区間に入るときも同様です。

長さが奇数の不定区間を飛び越える遷移は相殺されて \(0\) になります。長さが偶数の不定区間を飛び越える遷移は値を変えません。よって、長さが奇数の不定区間を飛び越える遷移を全て無視すればよいです。

これらの計算はすべて、分割統治FFTの際に遷移前や遷移後に \(1,0,-1\) のいずれかを掛けることで実現できます。よって、\(O(n(\log n)^2)\) でこの問題を解くことができました。\(n\leq\frac{N}{2}\) よりこれは十分高速です。実装の際は、不定区間が分割統治の前半と後半にまたがっているときに場合分けが必要なことに注意してください。