408451: GYM103119 H Fly Me To The Moon

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.

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 the number of different ways to fly to the Moon modulo $$$998\,244\,353$$$.

1 0
1

472799582

1 1
1
500 500

447362327

1 0
2

277036758

For the first sample case, the answer is $$$\binom{2000}{1000}$$$.

For the second sample case, the answer is $$$\binom{2000}{1000}-\binom{1000}{500}^2$$$.

Note that $$$\binom{n}{k}$$$ is a binomial coefficient, which gives the number of $$$k$$$-element subsets of an $$$n$$$-element set.