\(A,B,C\) に適切な線形変換を施すことで，\(0\)-indexed (値も \([0,N-1]\))かつ High-Elements に関する問題に変形できます．

順列のprefix-max階段凸包をUR (up,right) 列で考えてみます．

あるUR列に対し，それに対応する順列の個数とスコアの積を重みと呼ぶことにします．UR列に対し，以下の手順で適切な重みを付与することができます．

• 隣接 UR (High-element に対応)を S という記号に変えておく．
• 各 R をそれより左にあるいずれかの U とマッチさせ，完全マッチングを作る．これは UR 列に対する順列の個数を求めることに対応する．
• 各 S について，そこから左のいずれかの文字にリンクを伸ばすか，あるいはその S に終端記号を置く．リンク先の文字が U,R,S であるときはそれぞれ重み \(B\),\(A\),\(A+B\) で，リンクなしのときは重み \(C\) とする．これはスコアの式 \(A \times i + B \times p_i +C\) に対応する．

隣接 UR を全部 S に変える，という部分を，隣接 UR の部分集合を任意に選び S に変える，という操作に変えても，\(A,B\) の値を調整すれば同じ問題になります． 具体的には \(A \mathrel{+}=1,B \mathrel{-}=1\) とすればよいです． これは包除の操作で，後々で U,R,S を並べるときに，UR が隣接しないという条件を考えなくてよいようにしています．

こうして得た URS 列 + リンク は，森のような構造をなします． 一つの木は (U-R) ペアもしくは S を根とする木です． それぞれの木について，使った (R および S) の個数に関する指数型母関数を求めることができます． (U-R) ペアを根とする木に関する母関数を \(F(x)\)，S を根とする木に関する母関数を \(G(x)\) とおきます．

(U-R) ペアを使った個数を決め打つと，全体の (U,R,S) の個数がわかり，これらを並び替える方法も計算できるようになります． つまり，各 \(0 \leq k \leq N\) について，\([x^N] F(x)^k exp(G(x))\) を求めることができればよいです． これはpower-projection で解けます． 以上より，全体計算量 \(O(N \log^2N)\) でこの問題が解けます．

writer解