Mr. Panda and Circles
Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 65536/524288 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
Mr. Panda likes creating and solving mathematical puzzles. One day, Mr. Panda came up with a puzzle while he was playing the following game with Mrs. Panda:
In a plane, there are M points $(0,0),(1,0), ..,(M-2,0),(M-1,0)$ in a segment. You are also given $N$ circles, the radius of $i^{th}$ circle is $R_i$. In the game, you are allowed to put center of any circle into one of the $M$ points without making circles overlap (that is, if the intersection of their circles has a positive area).
An arrangement of circles is considered as valid if every circle’s center is in one of the $M$ points. Mr. Panda wanted to know length of empty units which are not covered by any circle in the segment from $(0,0)$ to $(M-1,0)$.
Because there are too many arrangements, Mr. Panda only wanted to know $\sum L_i^2$ modulo $1,000,000,007$ where $L_i$ is length of empty units in the $i^{th}$ arrangement.
The puzzle has confused Mr. Panda for a long time. Luckily, Mr. Panda knows you are in this contest. Could you help Mr. Panda’s solve the puzzle?
In a plane, there are M points $(0,0),(1,0), ..,(M-2,0),(M-1,0)$ in a segment. You are also given $N$ circles, the radius of $i^{th}$ circle is $R_i$. In the game, you are allowed to put center of any circle into one of the $M$ points without making circles overlap (that is, if the intersection of their circles has a positive area).
An arrangement of circles is considered as valid if every circle’s center is in one of the $M$ points. Mr. Panda wanted to know length of empty units which are not covered by any circle in the segment from $(0,0)$ to $(M-1,0)$.
Because there are too many arrangements, Mr. Panda only wanted to know $\sum L_i^2$ modulo $1,000,000,007$ where $L_i$ is length of empty units in the $i^{th}$ arrangement.
The puzzle has confused Mr. Panda for a long time. Luckily, Mr. Panda knows you are in this contest. Could you help Mr. Panda’s solve the puzzle?
Input
The first line of the input gives the number of test cases, $T$. $T$ test cases follow.
Each test case starts with a line consisting of two integers $N$, the number of circles, and $M$, the number
of points.
Then, a line consisting of $N$ integer numbers follows, the $i^{th}$ number $R_i$ indicates radius of the $i^{th}$ circle.
$1 \leq T \leq 50$
$1 \leq N \leq 10^5$
$2 \leq M \leq 10^{18}$
$1 \leq R_i \leq 10^5$
Each test case starts with a line consisting of two integers $N$, the number of circles, and $M$, the number
of points.
Then, a line consisting of $N$ integer numbers follows, the $i^{th}$ number $R_i$ indicates radius of the $i^{th}$ circle.
$1 \leq T \leq 50$
$1 \leq N \leq 10^5$
$2 \leq M \leq 10^{18}$
$1 \leq R_i \leq 10^5$
Output
For each test case, output one line containing “Case #x: y”, where $x$ is the test case number (starting from 1) and $y$ is the number that Mr. Panda wants to know for the $i^{th}$ input data set.
Sample Input
5 3 6 1 1 1 2 5 1 2 2 6 1 2 3 2 1 1 1 1 10 50
Sample Output
Case #1: 12 Case #2: 2 Case #3: 14 Case #4: 0 Case #5: 0
Source
2017中国大学生程序设计竞赛-总决赛-重现赛测试
Hint
