 # BIPIN3 - editorial

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

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.

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.

#include<studio.h>

#include<bits/stdc++.h>
#define ll long long
#define m 1000000007
using namespace std;

ll cal_power(ll a, ll b)
{
if(b==0)
return 1;
else if(b==1)
return a;
else
{
ll x=cal_power(a,b/2);
if(b%2==0)
return (x*x)%m;

``````   else
return (a*x*x)%m;
``````

}
}

int main()
{
ll t,i;
cin>>t;
while(t–)
{
ll z,col;
cin>>z>>col;
ll r=cal_power(col-1,z-1)%m;
cout<<((long long int)(r*col)%m)<<endl;
}
return 0;
}

plss tell mistake…!!!