ABC 401-500/ABC439F - Beautiful Kadomatsu - 競技プログラミング用 知識集積所

---

問題

ABC439F

必要知識

B以下レベルの内容は省略

• Fenwick木※
• 剰余類環

考え方

2つの条件を満たすiの位置は、必ず上下が交互に出現する。
つまり、条件を満たすのは上が先に出現し、最後も上が出現するとき。
さらに言い換えると、最初の2個が昇順で、最後の2個が降順になっているとき。

これは、取り出した数列の右から2番目がどこなのかで分類してカウントすることができる。
ある場所iについて、

• そこより左にA[i]より小さい値がL個ある
• そこより右にA[i]より小さい値がR個ある
• そこより左で、長さが2以上かつ最初の2つが昇順である部分列を作る方法がS通りある

だった場合、右から2番目がi番目である部分列で条件を満たすものは、

• 長さが3のものはL*R個
• 長さが4以上のものはS*R個

ある。
したがって、各iについてLとRとSを高速で求められれば、あとはその総和でよい。

LとRを求めるのはFenwick木※を使えば簡単。
Sの値は、S[i]=2*S[i-1]+L[i-1]で求められる。
というのは、Sに該当するものは、

• i番目を採用しないものはS[i-1]通り
• i番目を採用する長さ3以上のものはS[i-1]通り
• i番目を採用する長さ2のものはL[i-1]通り

であるから。
ということで、あとは先述の計算をすればよい。

答えはmod998244353での値なので、剰余類環も参照。

解答例

解答例

注意点

別解