No.2197 Same Dish
箱星
p-adicProblem Statement
The gyudon restaurant "Yukiya" serves $K$ kinds of dishes.
$N$ customers visit this restaurant. Customer $i$ arrives at time $L_i$ and leaves at time $R_i-0.1$. Each customer orders exactly $1$ dish.
There are $K^N$ ways for the $N$ customers to order. Among these, how many are such that, at some time, $2$ customers who ordered the same dish are in the restaurant simultaneously?
Find the answer modulo $998244353$.
Constraints
- $1\le N\le 10^5$
- $1\le K\le 10^9$
- $1\le L_i\lt R_i\le 2\times 10^5$
- All inputs are integers.
Input
$N$ $K$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$
Output
Find the number of ways of ordering that satisfy the condition, and output it modulo $998244353$.
Sample
Sample 1
Input
3 2 1 4 3 5 5 8
Output
4
Customers $1$ and $2$ are both in the restaurant at time $3$. Customer $3$ is never in the restaurant at the same time as customers $1,2$. Therefore, it suffices to count the ways of ordering in which customers $1,2$ order the same dish, and there are $2\times 2=4$ such ways.
Sample 2
Input
5 1 31 32 41 42 59 60 26 27 53 54
Output
0
No $2$ customers are in the restaurant at the same time.
Sample 3
Input
5 4 1 10 2 9 3 8 4 7 5 6
Output
1024
All customers are in the restaurant at time $5$. Also, since there are $5$ customers and $4$ kinds of dishes, some $2$ customers have ordered the same dish. Therefore, all ways of ordering satisfy the condition.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。