CRCLE_UI - Colorful Circle (EASY)
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.
3 3 Output: 6
For the first case, we have two sectors and three colors, here is all possibilities:
For second test case, we have three sector and three colors, here is all possibilities:
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 :)
Nailed it 0.00s :)
Tjandra , some more test cases please
@Tjandra: please look at my submission,why WA? ,submission id->9578731
@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....
@Tjandra my id is 9353125
thanks @Tjandra for Reply ... but still WA .... I think i can not AC this problem now :(
please @Tjandra ..can you look at my submission (id->9035872)...
@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.
I've also thougth about this problem, so
|Added by:||Tjandra Satria Gunawan|
|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|