MojaCoder will discontinue its service and shut down the judging system on December 31, 2026.

MaxMinSequence

2 secs 1024 MB

解説

包除原理を考えます

答えは

$X$ から $Y$ のいずれかの値をもつ長さ $N$ の数列の通りを $P$ 通り
$X-1$ から $Y$ のいずれかの値をもつ長さ $N$ の数列を $Q$ 通り
$X$ から $Y-1$ のいずれかの値をもつ長さ $N$ の数列 $R$ 通り
$X-1$ から $Y-1$ のいずれかの値をもつ長さ $N$ の数列 $S$ 通りとすると $P-(Q+R)+S$ となります。冪乗は $N$ の制約から繰り返し $2$ 乗をすると高速に求まリます。