BIPIN3 - editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Bipin Baburaj
Tester: Sergey Kulik
Editorialist: Mugurel Ionut Andreica

DIFFICULTY:

SIMPLE

PREREQUISITES:

Fast modular exponentiation

PROBLEM:

A rooted tree with N nodes is considered. We need to assign a color from 1 to K to each node of the tree in such a way that every pair of nodes (A,B), where A is the parent of B, has different colors.

QUICK EXPLANATION:

The answer is K*(K-1)^{N-1}. Note that the actual tree is not given. This is because there is the same answer for every tree with N nodes (and for the given K).

EXPLANATION:

We can choose any of the K colors for the root of the tree. Then we can choose any color except the root’s color for any of the root’s children. Then, for every child of a child of the root we can choose any color except that of its parent, and so on. Thus, for each of the other N-1 nodes we have K-1 choices for its color. The overall answer is K*(K-1)^{N-1}.

For subtasks 1 and 2 one can compute the answer in O(N) time. For subtask 3 one needs to compute (K-1)^{N-1} (modulo 10^9+7) using fast modular exponentiation, in O(log(N)) time.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

2

I have two solutions for the same problem. I applied the exponentiation by squaring method but got a TLE for the use of fmod instead of %. Can anyone explain me why the use of fmod gives a wrong answer but the use of % gets me an AC?
My custom _fmod function reads something like ::

    uint64_t _fmod(uint64_t x, uint64_t y)
    {
    #pragma STDC FENV_ACCESS ON
        uint64_t result = std::remainder(std::fabs(x), (y = std::fabs(y)));
        if (std::signbit(result)) result += y;
        return std::copysign(result, x);
    }

My accepted solution uses the % operator but I was hoping to get around the _fmod() function which is nothing but a variant of C++ fmod method.

3

#include<studio.h>