1598: TomCat的環(huán)
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 108 Solved: 28
[Submit][Status][Web Board]
Description

TomCat有一個環(huán)（如圖）有N個單元，并且有4中顏色。他希望把環(huán)的每一個單元格都染上顏色，但是相鄰的兩個單元格顏色不能相同。他想知道一共有幾種染色方法

Input

輸入單元格數(shù)N,N<=100000。

Output

輸出染色總數(shù)對1000000007取余的結(jié)果。

Sample Input

1
2

Sample Output

4
12

HINT

Source
/*
環(huán)形，區(qū)域數(shù)n，顏色種類m,涂色方法總數(shù)ans
m = 4;
n = 1, ans= 4 = m
n = 2, ans = 4 * 3 = 12 = m *(m-1)
n = 3,ans = 4 * 3 * 2 = 24
n = 4,ans = 84
//
n = 4,至少可用2種顏色，最多4顏色來圖，

m = 2,相當于只有兩個區(qū)域（同色的看成一塊區(qū)域），C(4,2) * A(2,2) = 6 * 2 = 12

m = 3, 2 * C(4,3) * A(3,3) = 8 * 6 = 48

m = 4, C(4,4) * A(4,4) = 1 * 24 = 24
所以n = 4, ans = 12 + 48 + 24 = 84;
//
n = 2,ans = 12 = 3^2 + 3
n = 3,ans = 24 = 3^3 -3
n = 4,ans = 84 = 3^4 + 3
…
推出，對于n > 1,
n為奇數(shù)，ans = (m-1)^n - (m-1)
n為偶數(shù)，ans = (m-1)^n + (m-1)

*/
Ac_code:

#include <stdio.h> #define LL long long const LL mod = 1e9 + 7; LL quickPow(LL a,LL b) {LL ans = 1;while(b){if(b&1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans; } int main() {LL N;while(~scanf("%lld",&N)){LL res;if(N == 1)res = 4;else {if(N % 2 == 0)res = (quickPow(3,N) + 3) % mod;elseres = (quickPow(3,N) - 3) % mod;}printf("%lld\n",res);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的1598: TomCat的环（快速幂+染色问题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。