DMOPC '21 Contest 7 P6 - Rainbow Subgraphs - Olympiads Online Judge

DMOPC '21 Contest 7 P6 - Rainbow Subgraphs

Points: 30 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

zhouzixiang2004

Problem type

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

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

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