上海市计算机学会竞赛平台2023年2月月赛丙组圆环三染色
发布时间
阅读量：
阅读量
题目描述
有一个圆环上有 𝑛n 个点，一个染色方案需要为每个点分配三种颜色中的一种，且圆环上相邻的点颜色不能相同。
请求出有多少种染色方案。答案可能很大，输出模 1,000,000,0071,000,000,007 的余数。
输入格式
- 单个整数表示 𝑛n。
输出格式
- 表示方案数模 1,000,000,0071,000,000,007 的余数。
数据范围
- 对于 30%30% 的数据，1≤𝑛≤201≤n≤20；
- 对于 60%60% 的数据，1≤𝑛≤1,000,0001≤n≤1,000,000；
- 对于 100%100% 的数据，1≤𝑛≤10181≤n≤1018
样例数据
输入:
1
输出:
3
输入:
3
输出:
6
详见代码:
#include<iostream>
#include<cstdio>
using namespace std;
const long long p=1000000007ll;
long long n;
struct Matrix
{
long long a[4][4];
void set1()
{
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
a[i][j]=(i==j);
return ;
}
void set0()
{
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
a[i][j]=0ll;
return ;
}
void modp()
{
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
a[i][j]%=p;
return ;
}
}mi;
Matrix operator *(const Matrix &as,const Matrix &bs)
{
Matrix rt;
rt.set0();
for(int k=1;k<=3;k++)
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
rt.a[i][j]+=as.a[i][k]*bs.a[k][j]%p;
rt.modp();
return rt;
}
Matrix qpw(Matrix as,long long bs)
{
Matrix rt;
rt.set1();
while(bs)
{
if(bs&1)
rt=rt*as;
as=as*as;
bs>>=1;
}
return rt;
}
int main()
{
scanf("%lld",&n);
if(n==1)
{
printf("%lld\n",3ll);
return 0;
}
Matrix mInit,mTran;
mInit.set0();
mTran.set0();
mInit.a[1][1]=1ll;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
if(i!=j)
mTran.a[i][j]=1ll;
mInit=mInit*qpw(mTran,n-1ll);
printf("%lld\n",((3*mInit.a[1][2]+3*mInit.a[1][3])%p+p)%p);
return 0;
}
全部评论 (0)
还没有任何评论哟~