Lucky Coins Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 415 Accepted Submission(s): 223
Problem Description
As we all know,every coin has two sides,with one side facing up and another side facing down.Now,We consider two coins's state is same if they both facing up or down.If we have N coins and put them in a line,all of us know that it
will be 2^N different ways.We call a "N coins sequence" as a Lucky Coins Sequence only if there exists more than two continuous coins's state are same.How many different Lucky Coins Sequences exist?
will be 2^N different ways.We call a "N coins sequence" as a Lucky Coins Sequence only if there exists more than two continuous coins's state are same.How many different Lucky Coins Sequences exist?
Input
There will be sevaral test cases.For each test case,the first line is only a positive integer n,which means n coins put in a line.Also,n not exceed 10^9.
Output
You should output the ways of lucky coins sequences exist with n coins ,but the answer will be very large,so you just output the answer module 10007.
Sample Input
3 4
Sample Output
2 6
Source
暴力打表后，队友们找到了规律
ANS=2^N-FN
其中Fn是斐波那契数列，只不过前两项为2和4
于是可以直接用矩阵二分快速求出斐波那契第n项，然后直接搞
我的代码：
#include<stdio.h>
#define mod 10007
struct mart
{
__int64 mat[3][3];
};
mart kk;
mart multi(mart a,mart b)
{
mart c;
__int64 i,j,k;
for(i=1;i<=2;i++)
for(j=1;j<=2;j++)
{
c.mat[i][j]=0;
for(k=1;k<=2;k++)
c.mat[i][j]=(c.mat[i][j]%mod+(a.mat[i][k]%mod)*(b.mat[k][j]%mod)%mod)%mod;
}
return c;
}
mart power(__int64 k)
{
mart p,q;
__int64 i,j;
for(i=1;i<=2;i++)
for(j=1;j<=2;j++)
{
p.mat[i][j]=kk.mat[i][j];
if(i==j)
q.mat[i][j]=1;
else
q.mat[i][j]=0;
}
if(k==0)
return q;
while(k!=1)
{
if(k&1)
{
k--;
q=multi(p,q);
}
else
{
k=k>>1;
p=multi(p,p);
}
}
p=multi(p,q);
return p;
}
__int64 POW(__int64 a,__int64 b)
{
__int64 ret=1;
for(;b;b>>=1,a=(a%mod)*(a%mod)%mod)
if(b&1)
ret=(ret%mod)*(a%mod)%mod;
return ret;
}
int main()
{
__int64 n,ans,oo;
mart xx;
while(scanf("%I64d",&n)!=EOF)
{
if(n==0||n==1||n==2)
{
printf("0\n");
continue;
}
kk.mat[1][1]=0;
kk.mat[1][2]=1;
kk.mat[2][1]=1;
kk.mat[2][2]=1;
xx=power(n-2);
ans=POW(2,n);
oo=((xx.mat[2][1]*2)%mod+(xx.mat[2][2]*4)%mod)%mod;
ans=((ans-oo)%mod+mod)%mod;
printf("%I64d\n",ans);
}
return 0;
}