[AGC012D] Colorful Balls
题意翻译
$N$ 个球排成一排,第 $i$ 个球的颜色为 $c_i$,重量为 $w_i$。我们定义「一次操作」为:选择两个颜色**相同**,且重量之和不超过 $X$ 的球,交换它们的位置;或选择两个颜色**不同**,且重量之和不超过 $Y$ 的球,交换它们的位置。问进行任意次操作后,可以得到多少种不同的颜色序列。输出答案对 $10^9+7$ 取模的结果。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc012/tasks/agc012_d
すぬけくんは $ N $ 個の色が塗られたボールを一列に並べました。 左から $ i $ 番目のボールは色 $ c_i $ で塗られていて、その重さは $ w_i $ です。
すぬけくんは以下の $ 2 $ 種類の操作を任意の順序で何回でも繰り返してボールの配置を変更することができます。
- 操作 $ 1 $:色が同じであるような $ 2 $ つのボールを選ぶ。$ 2 $ つのボールの重さの和が $ X $ 以下なら、$ 2 $ つのボールの位置を入れ替える。
- 操作 $ 2 $:色が異なるような $ 2 $ つのボールを選ぶ。$ 2 $ つのボールの重さの和が $ Y $ 以下なら、$ 2 $ つのボールの位置を入れ替える。
最終的なボールの色の並びとしてありうるような数列の数を modulo $ 10^9\ +\ 7 $ で求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ X $ $ Y $ $ c_1 $ $ w_1 $ $ : $ $ c_N $ $ w_N $
输出格式
答えを出力せよ。
输入输出样例
输入样例 #1
4 7 3
3 2
4 3
2 1
4 4
输出样例 #1
2
输入样例 #2
1 1 1
1 1
输出样例 #2
1
输入样例 #3
21 77 68
16 73
16 99
19 66
2 87
2 16
7 17
10 36
10 68
2 38
10 74
13 55
21 21
3 7
12 41
13 88
18 6
2 12
13 87
1 9
2 27
13 15
输出样例 #3
129729600
说明
### 制約
- $ 1\ ≦\ N\ ≦\ 2\ ×\ 10^5 $
- $ 1\ ≦\ X,\ Y\ ≦\ 10^9 $
- $ 1\ ≦\ c_i\ ≦\ N $
- $ 1\ ≦\ w_i\ ≦\ 10^9 $
- $ X,Y,c_i,\ w_i $ はいずれも整数
### Sample Explanation 1
\- 操作 $ 2 $ により左から $ 1 $ 番目のボールの位置と左から $ 3 $ 番目のボールの位置を入れ替えることで、$ (2,4,3,4) $ という色の並びを作ることが可能です。 - 操作 $ 1 $ により左から $ 2 $ 番目のボールの位置と左から $ 4 $ 番目のボールの位置を入れ替えることも可能ですが、色の並びは変化しません。