Vrijeme: 08:49
Bojanka | Coloring Book #1
Zadan je neusmjeren graf s
čvorova označenih redom od
do
. Postoji brid između čvorova
i
za sve prirodne brojeve
.
Na koliko načina možemo obojiti svaki čvor danog grafa u jednu od
različitih boja tako da ne postoji brid čiji su vrhovi iste boje? Odgovor napišite modulo
.
![n = 100](/media/m/2/4/e/24e415b37d76f43b87cfcfbef56a7a1b.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
![k + 1](/media/m/6/4/d/64da3643b8a09aa96732cb51d9207b6d.png)
![1 \leq k < n](/media/m/2/2/0/220cdf9115a5f65ee370085078b50d07.png)
Na koliko načina možemo obojiti svaki čvor danog grafa u jednu od
![2021](/media/m/1/2/e/12eab82b81aa188baaf9c8a56b863e71.png)
![1000000007](/media/m/7/b/a/7babf654238f19ca23838cea4bc58bdc.png)
An undirected graph with
nodes is given. The nodes are labeled with integers from
to
. There is an edge between nodes
and
for every integer
.
In how many ways can we color each node in one of
different colors such that there is no edge whose nodes are the same color? Write the answer modulo
.
![n = 100](/media/m/2/4/e/24e415b37d76f43b87cfcfbef56a7a1b.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
![k + 1](/media/m/6/4/d/64da3643b8a09aa96732cb51d9207b6d.png)
![1 \leq k < n](/media/m/2/2/0/220cdf9115a5f65ee370085078b50d07.png)
In how many ways can we color each node in one of
![2021](/media/m/1/2/e/12eab82b81aa188baaf9c8a56b863e71.png)
![1000000007](/media/m/7/b/a/7babf654238f19ca23838cea4bc58bdc.png)