ARC 201-300/ARC203C - Destruction of Walls - 競技プログラミング用 知識集積所

---

問題

ARC203C

必要知識

簡単な内容は省略

• 順列組み合わせ※
• 剰余類環
• 繰り返し二乗法※

考え方

露骨に太字で書いてある制約がポイント。
左下から右下まで行くのに、最低でもh+w-2枚の壁を破壊しなければならないので、無駄に破壊できるのは2枚まで。
そこで、kの値で場合分けして考える。

k==h+w-2のとき。
h+w-2回のうち、h-1回「下へ」、w-1回「右へ」、とするしかない。
よって、順列組み合わせ※の考えで、(h+w-2)! / {(h-1)!*(w-1)!} 通り。

k==h+w-1のとき。
h+w-2回のうち、h-1回「下へ」、w-1回「右へ」、とする必要経路と、無駄に1枚破壊。
まず経路が順列組み合わせ※の考えで、(h+w-2)! / {(h-1)!*(w-1)!} 通り。
無駄に破壊する1枚の壁の選び方は、まだ残っている壁の枚数分。
左右移動を阻害する壁が、もともとh*(w-1)枚のところ、w-1枚壊されているので残り(h-1)*(w-1)枚。
上下移動を阻害する壁が、もともと(h-1)*w枚のところ、h-1枚壊されているので残り(h-1)*(w-1)枚。
あわせて2*(h-1)*(w-1)枚なので、これを経路数に掛ける。

k==h+wのとき。
これには3パターンある。

まず、h+w-2回のうち、h-1回「下へ」、w-1回「右へ」、とする必要経路と、無駄に2枚破壊。
まず経路が順列組み合わせ※の考えで、(h+w-2)! / {(h-1)!*(w-1)!} 通り。
これに、無駄に破壊する2枚の壁の選び方 2*(h-1)*(w-1) * {2*(h-1)*(w-1)-1} / 2を掛ける。
ところが、無駄に壊した2枚が曲がり角の内側にある2枚だった場合、別の経路から作った図と一致してしまうことがある。
これは、h+w-3回のうち、h-2回「下へ」、w-2回「右へ」、1回「下右or右下」と考えることができる。
つまり、(h+w-3)! / {(h-2)!*(w-2)!} 通りが余計にカウントされていくので、これを引く。

次に、h+w回のうち、h回「下へ」、1回「上へ」、w-1回「右へ」、というパターン。
これは、以下の制約がかかる。

• 「上へ」の直前直後は必ず「右へ」でなければならない（でないと、無駄破壊パターンになる）
• 「上へ」より前に少なくとも「下へ」が1つなければならない
• 「上へ」より後に少なくとも「下へ」が1つなければならない

これは、順列組み合わせ※の工夫で対応できる。
まず、h+1個の「下へ」とw-3個の「右へ」を並べる。
その後、「下へ」のうち最初と最後を除いたh-1個のうち1つを「右上右」に変える。
ということは、これは　(h-1) * (h+w-2)! / {(h+1)!*(w-3)!} 通り

最後に、h+w回のうち、h-1回「下へ」、w回「右へ」、1回「左へ」というパターン。
これは、前項目のhとwを入れ替えるだけ。

そして、これら3つの経路を足せば答えである。

答えは998244353で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を%998244353し、割り算は代わりに998244353-2乗したものを掛ける。
累乗計算を何度も行うため、繰り返し二乗法※のアルゴリズムも用意しておくこと。

解答例

解答例

注意点

hやwが2個のときに注意

一度戻るパターンのときに、式にそのままつっこむと-1の階乗がでてきて大変なことになる。
戻るパターンの計算は3以上のときだけにすること。

壁の数が意外と多い

2*(h-1)*(w-1)が意外と大きく、組み合わせ計算前にmodを取っておかないとlong long型から溢れる。

別解