DMOPC '21 Contest 7 P6 - Rainbow Subgraphs

View as PDF

Submit solution


Points: 30 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

You are given positive integers N, M, and MOD.

Let V be the set of points (x,y) in the plane such that x and y are integers, y \ge 0, and N^2 \le x^2+y^2 < (N+M)^2. Let E be a set of undirected edges between elements of V, where (u,v) \in E if point u and point v are distance 1 apart.

Calculate the number of subgraphs of the graph G = (V,E), modulo MOD. That is, the number of pairs (V',E') such that V' \subseteq V, E' \subseteq E, and u,v \in V' for all (u,v) \in E'. Note that V' and/or E' are allowed to be empty or equal to V or E respectively.

Constraints

1 \le N \le 300

1 \le M \le 16

10^8 \le MOD \le 10^9

Subtask 1 [20%]

1 \le N \le 10

1 \le M \le 5

Subtask 2 [20%]

1 \le N \le 35

1 \le M \le 5

Subtask 3 [20%]

1 \le N \le 100

1 \le M \le 5

Subtask 4 [20%]

1 \le N \le 200

1 \le M \le 10

Subtask 5 [20%]

No additional constraints.

Input Specification

The first and only line of input contains three space-separated integers: N, M, and MOD.

Output Specification

Output the number of subgraphs modulo MOD.

Sample Input 1

1 1 998244352

Sample Output 1

89

Explanation for Sample 1

The graph G looks like the following:

Sample Input 2

2 2 998244352

Sample Output 2

41377047

Explanation for Sample 2

The graph G looks like the following:

Sample Input 3

31 4 159265358

Sample Output 3

54714600

Comments

There are no comments at the moment.