圆环三染色
内存限制: 256 Mb时间限制: 1000 ms
题目描述
有一个圆环上有 n 个点，一个染色方案需要为每个点分配三种颜色中的一种，且圆环上相邻的点颜色不能相同。
请求出有多少种染色方案。答案可能很大，输出模 1,000,000,007 的余数。
输入格式
单个整数表示 n。
输出格式
表示方案数模 1,000,000,007 的余数。
数据范围
对于 30% 的数据，1≤n≤20；
对于 60% 的数据，1≤n≤1,000,000；
对于 100% 的数据，1≤n≤1018
样例数据
输入:
1
输出:
3
输入:
3
输出:
6
题解
第 1 个点 3种颜色任选，a[1]=3;
第 2~n-1 个点，都有 2 种颜色可选，a[i]=2; (1<i<n)
第 n 个点：如果 a[1]==a[n-1], a[n]=2;
如果 a[1]!=a[n-1], a[n]=1;
f[n][1]表示 a[n]==a[1]的情况： f[n][1] = f[n-1][0]
f[n][0]表示 a[n]！=a[1]的情况：f[n][0] = f[n-1][0] + 2*f[n-1][1] = f[n-1][0]+2*f[n-2][0]
总结答案规律 :
f[n] = 2*f[n-2]+f[n-1] (n>=4)
初始条件：
f[1] = 3
f[2] = 6
f[3] = 6
3 6 6 18 30 66 126 …
int f[1000000000000000005];
大太，无法创建DP数组 改为迭代，但依然只能过6个点，还有4个点超时
再次寻找答案规律
12345678910
3661830661262585101026 ……
当 n>3时：
n偶：2^n +2
n奇：2^n -2
计算2^n：快速幂
递推代码（60分）
#include <bits/stdc++.h>
using namespace std;
long long M = 1000000007;
int main()
{
long long n, a,b,c;
cin>>n;
if(n==1) {
cout<<3;
return 0;
}
if(n==2 || n==3){
cout<<6;
return 0;
}
//初始化
a = 6, b=6;
for(int i=4; i<=n; i++){
c = (2*a+b)%M;
a = b;
b = c;
}
cout<<c;
return 0;
}快速幂代码（AC）
#include <bits/stdc++.h>
using namespace std;
long long M = 1000000007;
long long fast(long long n){
if(n==1)return 2;
long long t=fast(n/2);
if(n%2==0)return t*t%M;
return t*t%M*2%M;
}
int main()
{
long long n;
cin>>n;
if(n==1) {
cout<<3;
return 0;
}
if(n==2 || n==3){
cout<<6;
return 0;
}
if(n%2==0){
cout<<(fast(n)+2)%M;
}
else{
cout<<(fast(n)-2+M)%M;
}
return 0;
}