問題一覧 > 通常問題

No.2197 Same Dish

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 86
作問者 : koboshikoboshi / テスター : p-adicp-adic
3 ProblemId : 6762 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-28 16:43:45

問題文

牛丼店「ゆき家」には $K$ 種類の料理があります。

この店に客が $N$ 人来店します。客 $i$ は時刻 $L_i$ に来店し、時刻 $R_i-0.1$ に退店します。どの客も料理を $1$ つだけ注文します。

$N$ 人の客の注文の仕方は $K^N$ 通りありますが、このうちある時刻において同じ料理を注文している $2$ 人が同時に店内に存在するようなものは何通りありますか。

答えを $998244353$ で割った余りを求めてください。

制約

  • $1\le N\le 10^5$
  • $1\le K\le 10^9$
  • $1\le L_i\lt R_i\le 2\times 10^5$
  • 入力はすべて整数

入力

$N$ $K$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

出力

条件を満たす注文の仕方が何通りあるかを求め、$998244353$ で割った余りを出力してください。

サンプル

サンプル1
入力
3 2
1 4
3 5
5 8
出力
4

客 $1$ と客 $2$ は時刻 $3$ において同時に店にいます。客 $3$ は客 $1,2$ と同時に店にいることはありません。よって、客 $1,2$ が同じ料理を注文しているような注文の仕方の数を求めればよく、それは $2\times 2=4$ 通りです。

サンプル2
入力
5 1
31 32
41 42
59 60
26 27
53 54
出力
0

どの $2$ 人も同じ時刻に店にいません。

サンプル3
入力
5 4
1 10
2 9
3 8
4 7
5 6
出力
1024

どの客も時刻 $5$ において店にいます。また、客が $5$ 人で料理が $4$ 種類なので、ある $2$ 人は同じ料理を注文しています。よってすべての注文の仕方が条件を満たします。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。