CRCLE_UI - Colorful Circle (EASY)

no tags 

I take this problem from my midterm exam today, because for me and some of my friends it's interesting, so I decided to translated this problem into english and upload this problem to SPOJ. See the original problem in indonesian language here.

Given N sectors where 1<N<101000, from a circle that sown in the picture below:


We will color each sector with K different colors, where 2<K<101000 such that each sector colored with one color and each adjacent sector must have different color. Your task is to count how many ways to color all that sectors.


First line, there is a number T(0<T<1000) denoting number of test cases, then T lines follow.
each line containing two integers: N and K separated by a space.


For each test case, output number of ways to color the circle, since the number can be too large, take modulo 109+7.


2 3
3 3



For the first case, we have two sectors and three colors, here is all possibilities:

2 sectors 3 colors

For second test case, we have three sector and three colors, here is all possibilities:

3 sectors 3 colors


Time limit set so that ~128 Bytes of python 3 code can get accepted, also my C top speed program AC in 0.12s
Have fun :) 


See also: Another problem added by Tjandra Satria Gunawan

hide comments
julkas: 2018-07-06 14:25:42

Good problem.

hanstan: 2017-07-13 08:15:09

Nailed it 0.00s :)

Itachi_Uchiha: 2015-01-23 05:45:42

Tjandra , some more test cases please
for hugh numbers

Viplov Jain: 2013-07-01 21:20:37

@Tjandra: please look at my submission,why WA? ,submission id->9578731
never mind, i got it ,was using the wrong formula
got AC :)

Last edit: 2013-07-07 02:41:42
Yashpal: 2013-06-05 18:42:04

@Tjandra:if i hav to calculate the no. of ways to color the n sectors with all the k -colors or taken some colors at a time.....i.e if k<=n or not....

maradona: 2013-05-27 08:55:53

@Tjandra my id is 9353125
ًWhy slow ???
<u><b>Ans</b></u>: Your formula isn't fast enough.

<u><b>Edit</b></u>: It's really along time but i like this :(.
Another thing spoj is very disappointed for java programmers.

Last edit: 2014-12-31 21:30:44
abdou_93: 2013-04-06 08:56:32

thanks @Tjandra for Reply ... but still WA .... I think i can not AC this problem now :(

finally solved :D..

Last edit: 2013-05-23 13:25:10
abdou_93: 2013-04-04 11:20:23

please @Tjandra ..can you look at my submission (id->9035872)...
thanks what ever :D
Ans: You getting WA because in your program output there are many negative value.

Last edit: 2013-04-06 00:29:06
Avinash Thummala: 2013-01-16 10:28:01

@Tjandra If possible please have a look at my submission (id->8509987). Quite new to Python, but used it anyway as I thought that Montgomery reduction would be useful.
Not really sure how I can optimize even further. Would definitely appreciate a hint.
Ans: Sorry but formula that you've used is incorrect... And to speed up your code try to reduce mod operations...

Last edit: 2013-01-19 11:26:00
YangYue: 2013-01-01 03:21:24

I've also thougth about this problem, so
it's easy for me :-)

Added by:Tjandra Satria Gunawan
Time limit:0.170s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Discrete Math II, Midterm exam, question number 4, University of Indonesia, 14 November 2012 | Translated by: Tjandra