Educational Codeforces Round 83 D. Count the Arrays : 組み合わせ

とてもとても面白い問題でした！こういう考察楽しい。
https://codeforces.com/contest/1312/problem/D

hitonanodeさんのSubmitがとても分かりやすくて参考になりました。
https://codeforces.com/contest/1312/submission/72804437

題意

a. n個の1以上の整数要素からなる配列が与えられる。また、正の整数mも与えられる。
b. この配列はあるi番目に最大となる値があり、その左側は(0から見て)単調増加であり、その右側は単調減少である。以下、ピーク、と呼ぶ。
c. この配列には1つだけ同じ数字のペアがある。
d. このような数列が何通りあるか？modで述べよ。

例

$n=4, m=5$のいくつかを考える。

• $[1,2,3,1]$
• $[1,4,2,1]$
• $[2,4,3,2]$

単調減少、単調増加が条件であり、以下のように、同じ値が続くのはNGである。

• $[2,2,3,1]$

また、題意より、以下のように、単調増加・減少区間がない数列もNGである。

• $[1,2,3,4]$
• $[4,3,2,1]$

問題を言い換える

上記はn=6でiが7のイメージ。(iはピークの値であり、mそのものではない(後述)

• あるピーク値iがある(図中黒の7)

• (その値は最大であるから) i-1以下の数字jを1つ選び、その値はピークの左右に配置される。(図中緑)

  • 単調増加区間、単調減少区間に同じ数字が2回以上は存在できないから

• jではないi-1以下の数字をn-3つ選ぶ(つまり、i-2個の中から3つ)(図中赤)

  • ピークの値kを1つとペアの数字jを2つ選んでいるのでnの長さの配列に入れないといけない要素はn-3つ。

• この選んだ数字をピーク値の右側に分配するか、左側に分配するかを選択する。(図中黄色)

  • 上記のようにピークの左右には最低1つの数字を入れないとならないが、これらの数字はすべて右側に入れても左側に入れても良い。なぜなら、ペアjを選択した時点ですでに左右に最低1つの数字があるため、左右の要素が最低1つは残る。

これらの計算をiが $(n - 1)$ から $ m $まで行えばよい。もし、iがn-2(以下)だとすると、数字を選ぶことが出来ない
- 例: n=6で i=5なら$[1, 5, 4, 3, 2, 1]$
- 例: n=6で i=4なら$[1, 4, 3, 2, 1, ???]$となってしまう

実装

$$ \sum_{i=(n-1)}^{m} (i-1) \cdot {}_{(i-2)}C _{(n-3)} \cdot 2^{(n-3)}$$
で終わり！すごい。

• $n,r$が$2 \cdot 10^{5}$程度のmodな$nCr$をforで回すので、逆元なり各種結果をキャッシュしておかないとTLEします。

# https://www.planeta.tokyo/entry/5195/
mod = 998244353

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p

p = mod
N = 5 * 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


n, m = map(int, input().split())
res = 0
import math
if n == 2:
    print(0)
else:
    for i in range(n-1, m+1):
        res += (i - 1) * cmb(i - 2, n - 3, mod) * pow(2, n-3, mod)
        res %= mod
    print(res)

おまけ: NGアプローチ

言い換えをしないで整理しようとしたところ方向性を見失った。