一站到底第一题就刷到这个。。。
详见表格
f=16
p3=1 8 27 64 125 216
add=7 19 37 61 91
gc3=12 18 24 30
p2=1 4 9 16 25 36
gc2=3 5 7 9 11 13
1=1
i=i-1+1
gc2_i=gc2_{i-1}+2
p2_i=p2_{i-1}+gc2_{i-1}
gc3_i=gc3_{i-1}+6
add_i=add_{i-1}+gc3_{i-1}
p3_i=p3_{i-1}+add_{i-1}
f_{i-1}=f_{i-1}
f_i=f_{i-1}+f_{i-2}+p3_{i-1}+add_{i-1}+p2_{i-1}+gc2_{i-1}+i-1+2
p3=1 8 27 64 125 216
add=7 19 37 61 91
gc3=12 18 24 30
p2=1 4 9 16 25 36
gc2=3 5 7 9 11 13
1=1
i=i-1+1
gc2_i=gc2_{i-1}+2
p2_i=p2_{i-1}+gc2_{i-1}
gc3_i=gc3_{i-1}+6
add_i=add_{i-1}+gc3_{i-1}
p3_i=p3_{i-1}+add_{i-1}
f_{i-1}=f_{i-1}
f_i=f_{i-1}+f_{i-2}+p3_{i-1}+add_{i-1}+p2_{i-1}+gc2_{i-1}+i-1+2
标程:
#include<cstdio>
#include<cstring>
#define ymw 1000000007
using namespace std;int t;
long long n;
struct node{long long a[9][9];};
const int d[9][9]=
{
{1,1,2,6,0,0,0,0,2},
{0,1,0,0,0,0,0,0,1},
{0,0,1,0,0,1,0,0,1},
{0,0,0,1,1,0,0,0,0},
{0,0,0,0,1,0,1,0,1},
{0,0,0,0,0,1,0,0,1},
{0,0,0,0,0,0,1,0,1},
{0,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,1,1},
};
const int e[9]={1,2,5,18,19,4,8,1,16};
inline node mul(node x,node y)
{
node z;
memset(&z,0,sizeof(z));
for(register int i=0;i<9;i++)
for(register int j=0;j<9;j++)
for(register int k=0;k<9;k++)
z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%ymw)%ymw;
return z;
}
inline long long ksm(register long long y)
{
node x,ans;
memset(&x,0,sizeof(x));
memset(&ans,0,sizeof(ans));
for(register int i=0;i<9;i++)
for(register int j=0;j<9;j++)
x.a[i][j]=d[i][j];
for(register int i=0;i<9;i++) ans.a[0][i]=e[i];
while(y)
{
if(y&1) ans=mul(ans,x);
x=mul(x,x);
y>>=1;
}
return ans.a[0][8];
}
signed main()
{
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
if(n==0) putchar(48);
else if(n==1) putchar(49);
else printf("%lld",ksm(n-2));
putchar(10);
}
}
#include<cstring>
#define ymw 1000000007
using namespace std;int t;
long long n;
struct node{long long a[9][9];};
const int d[9][9]=
{
{1,1,2,6,0,0,0,0,2},
{0,1,0,0,0,0,0,0,1},
{0,0,1,0,0,1,0,0,1},
{0,0,0,1,1,0,0,0,0},
{0,0,0,0,1,0,1,0,1},
{0,0,0,0,0,1,0,0,1},
{0,0,0,0,0,0,1,0,1},
{0,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,1,1},
};
const int e[9]={1,2,5,18,19,4,8,1,16};
inline node mul(node x,node y)
{
node z;
memset(&z,0,sizeof(z));
for(register int i=0;i<9;i++)
for(register int j=0;j<9;j++)
for(register int k=0;k<9;k++)
z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%ymw)%ymw;
return z;
}
inline long long ksm(register long long y)
{
node x,ans;
memset(&x,0,sizeof(x));
memset(&ans,0,sizeof(ans));
for(register int i=0;i<9;i++)
for(register int j=0;j<9;j++)
x.a[i][j]=d[i][j];
for(register int i=0;i<9;i++) ans.a[0][i]=e[i];
while(y)
{
if(y&1) ans=mul(ans,x);
x=mul(x,x);
y>>=1;
}
return ans.a[0][8];
}
signed main()
{
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
if(n==0) putchar(48);
else if(n==1) putchar(49);
else printf("%lld",ksm(n-2));
putchar(10);
}
}
全部评论
(0) 回帖