5614: Problem H. Fly Me To The Moon
[Creator : ]
Description
In order to unravel the mystery of their life experience, Nasa and Tsukasa plan to fly to the Moon with the help of spacecrafts from the Earth. When calculating and simulating the flight orbit of the spacecrafts, they assume that the Earth is located at $(0,0)$ and the Moon is located at $(1000,1000)$ in the universe.
Although the whole journey is so long and difficult, thanks to advanced aerospace technology, there are space stations at all positions with integer coordinates except the Earth and the Moon in the universe. So they can take a break on their long journey and interchange other spacecrafts in these stations.
There are $n$ types of brand new spacecrafts in each space station, and the $i$-th type of spacecrafts can take $d_i$ units of fuels and always fly towards the Moon for reducing cost. More precisely, they can sail from $(x,y)$ to $(x+dx,y+dy)$, where $dx$ and $dy$ are non-negative integers and $0 < dx^2+dy^2 \le d_i^2$, with the $i$-th type of spacecrafts.
During the journey, they can choose whether to land on some space stations and have a rest. Note that if they choose to take a break in a space station, they will change to a new spacecraft in that space station when they set off.
However, recently $m$ space stations are closed for maintenance, and they cannot stay on these closed stations. Also the spacecrafts in these closed stations are not available, too. Out of concerns about this matter, Nasa is worried whether they could reach the moon successfully.
Therefore, they turn to seek your assistance. You need to help them calculate the number of different ways to fly to the Moon. Since the answer may be too large, you only need to output the answer modulo $998\,244\,353$. Note that two ways are considered different if there exists a stage such that they choose two different types of spacecraft or fly towards two different space stations.
Although the whole journey is so long and difficult, thanks to advanced aerospace technology, there are space stations at all positions with integer coordinates except the Earth and the Moon in the universe. So they can take a break on their long journey and interchange other spacecrafts in these stations.
There are $n$ types of brand new spacecrafts in each space station, and the $i$-th type of spacecrafts can take $d_i$ units of fuels and always fly towards the Moon for reducing cost. More precisely, they can sail from $(x,y)$ to $(x+dx,y+dy)$, where $dx$ and $dy$ are non-negative integers and $0 < dx^2+dy^2 \le d_i^2$, with the $i$-th type of spacecrafts.
During the journey, they can choose whether to land on some space stations and have a rest. Note that if they choose to take a break in a space station, they will change to a new spacecraft in that space station when they set off.
However, recently $m$ space stations are closed for maintenance, and they cannot stay on these closed stations. Also the spacecrafts in these closed stations are not available, too. Out of concerns about this matter, Nasa is worried whether they could reach the moon successfully.
Therefore, they turn to seek your assistance. You need to help them calculate the number of different ways to fly to the Moon. Since the answer may be too large, you only need to output the answer modulo $998\,244\,353$. Note that two ways are considered different if there exists a stage such that they choose two different types of spacecraft or fly towards two different space stations.
Input
The first line of the input contains two integers $n$ $(1 \le n \le 1000)$ and $m$ $(0 \le m \le 1000)$, indicating the number of spacecrafts in each space station and the number of closed space stations in the universe.
Then the second line contains $n$ integers $d_1,d_2,\cdots,d_n$ $(1 \le d_i \le 1000)$, indicating the units of fuels that each type of spacecrafts can take.
Each of the following $m$ lines contain two integers $x$ and $y$ $(0 \le x, y \le 1000)$, indicating the space station at $(x,y)$ is closed. It is guaranteed that the given $m$ locations are not the same as the locations of the Earth and the Moon and they are pairwise distinct.
Output
Output the number of different ways to fly to the Moon modulo $998,244,353$.
Sample 1 Input
1 0
1
Sample 1 Output
472799582
the answer is $\binom{2000}{1000}$.
Sample 2 Input
1 1
1
500 500
Sample 2 Output
447362327
the answer is $\binom{2000}{1000}-\binom{1000}{500}^2$.
Sample 3 Input
1 0
2
Sample 3 Output
277036758
HINT
that $\binom{n}{k}$ is a binomial coefficient, which gives the number of $k$-element subsets of an $n$-element set.
题目来源：2021年5月29日 ICPC 澳门分站赛。
题目来源：2021年5月29日 ICPC 澳门分站赛。