/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1200 点
問題文
長さ N の非負整数列 A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N) が与えられます。
(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) に対して、P のコストを \sum_{i=1}^{N} \left \lfloor \frac{A_{P_i}}{2^{B_i}} \right \rfloor と定義します。
コストの最小値を達成する P の個数を 998244353 で割った余りを求めてください。
T 個のテストケースが与えられるので、それぞれについて解いてください。
制約
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 0 \le B_i \le 30
- 全てのテストケースにおける N の総和は 2 \times 10^5 以下
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N A_1\ A_2\ \dots\ A_N B_1\ B_2\ \dots\ B_N
出力
T 行出力せよ。i(1 \le i \le T) 行目には \mathrm{case}_i の答えを出力せよ。
入力例 1
7 2 5 9 0 1 3 3 4 10 0 1 2 4 1 2 3 4 0 0 1 1 5 1000000000 1000000000 1000000000 1000000000 1000000000 0 0 0 0 0 11 19 68 97 62 99 52 57 19 43 80 96 5 3 3 2 3 4 3 2 3 4 3 14 86 49 83 31 5 43 7 46 98 36 60 4 69 59 3 1 4 4 4 0 1 3 0 4 3 5 1 2 10 907139744 237517128 852012347 350549430 62876062 196019710 263351472 184393437 281593038 753973502 23 12 1 26 29 24 0 7 10 4
出力例 1
1 2 4 120 8640 15552 1
1 個目のテストケースについては、各 P に対するコストは以下のようになります。
- P=(1,2) のとき、\left \lfloor \frac{A_{1}}{2^{B_1}} \right \rfloor + \left \lfloor \frac{A_{2}}{2^{B_2}} \right \rfloor = \left \lfloor \frac{5}{1} \right \rfloor + \left \lfloor \frac{9}{2} \right \rfloor = 9
- P=(2,1) のとき、\left \lfloor \frac{A_{2}}{2^{B_1}} \right \rfloor + \left \lfloor \frac{A_{1}}{2^{B_2}} \right \rfloor = \left \lfloor \frac{9}{1} \right \rfloor + \left \lfloor \frac{5}{2} \right \rfloor = 11
よって、コストの最小値は 9 であり、それを達成する P は (1,2) の 1 個です。
2 個目のテストケースについては、P = (1,2,3),(2,1,3) がコストの最小値 7 を達成します。
3 個目のテストケースについては、P = (1,2,3,4),(2,1,3,4),(1,2,4,3),(2,1,4,3) がコストの最小値 6 を達成します。
4 個目のテストケースについては、(1,2,3,4,5) の順列全てがコストの最小値 5000000000 を達成します。
Score : 1200 points
Problem Statement
You are given two length-N sequences of non-negative integers: A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).
For a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N), define the cost of P as \sum_{i=1}^{N} \left \lfloor \frac{A_{P_i}}{2^{B_i}} \right \rfloor.
Find the number, modulo 998244353, of permutations P that achieve the minimum cost.
You are given T test cases; solve each of them.
Constraints
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 0 \le B_i \le 30
- The sum of N over all test cases is at most 2 \times 10^5.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N A_1\ A_2\ \dots\ A_N B_1\ B_2\ \dots\ B_N
Output
Output T lines. The i-th line (1 \le i \le T) should contain the answer for \mathrm{case}_i.
Sample Input 1
7 2 5 9 0 1 3 3 4 10 0 1 2 4 1 2 3 4 0 0 1 1 5 1000000000 1000000000 1000000000 1000000000 1000000000 0 0 0 0 0 11 19 68 97 62 99 52 57 19 43 80 96 5 3 3 2 3 4 3 2 3 4 3 14 86 49 83 31 5 43 7 46 98 36 60 4 69 59 3 1 4 4 4 0 1 3 0 4 3 5 1 2 10 907139744 237517128 852012347 350549430 62876062 196019710 263351472 184393437 281593038 753973502 23 12 1 26 29 24 0 7 10 4
Sample Output 1
1 2 4 120 8640 15552 1
For the first test case, the cost for each P is as follows:
- For P=(1,2), \left \lfloor \frac{A_{1}}{2^{B_1}} \right \rfloor + \left \lfloor \frac{A_{2}}{2^{B_2}} \right \rfloor = \left \lfloor \frac{5}{1} \right \rfloor + \left \lfloor \frac{9}{2} \right \rfloor = 9
- For P=(2,1), \left \lfloor \frac{A_{2}}{2^{B_1}} \right \rfloor + \left \lfloor \frac{A_{1}}{2^{B_2}} \right \rfloor = \left \lfloor \frac{9}{1} \right \rfloor + \left \lfloor \frac{5}{2} \right \rfloor = 11
Thus, the minimum cost is 9, and there is one permutation P = (1,2) that achieves it.
For the second test case, P = (1,2,3),(2,1,3) achieve the minimum cost of 7.
For the third test case, P = (1,2,3,4),(2,1,3,4),(1,2,4,3),(2,1,4,3) achieve the minimum cost of 6.
For the fourth test case, all permutations of (1,2,3,4,5) achieve the minimum cost of 5000000000.