「NOIP模拟赛」数列
「题目描述」
a[1]=a[2]=a[3]=1
a[x]=a[x-3]+a[x-1] (x>3)
求a数列的第n项对1000000007（10^9+7）取余的值。
「输入格式」
第一行一个整数T，表示询问个数。
以下T行，每行一个正整数n。
「输出格式」
每行输出一个非负整数表示答案。
「样例输入」
3
6
8
10
「样例输出」
4
9
19
「数据范围」
对于30%的数据 n<=100；
对于60%的数据 n<=2*10^7；
对于100%的数据 T<=100，n<=2*10^9；
题解
这个可以直接矩阵乘法搞掉。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<iostream> #include<cstdio> #include<cstring> #define ll long long #define mod 1000000007 using namespace std; int T; ll a[4][4],b[4][4]; ll n; ll read() { char ch=getchar(); ll f=1,x=0; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();} return x*f; } void mul(ll a[4][4],ll b[4][4],ll ans[4][4]) { ll tmp[4][4]; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) { tmp[i][j]=0; for(int k=1;k<=3;k++) tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod; } for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) ans[i][j]=tmp[i][j]; } int main() { //freopen("seq.in","r",stdin); //freopen("seq.out","w",stdout); T=read(); for(int l=1;l<=T;l++) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i=1;i<=3;i++)a[i][i]=1; b[1][3]=b[2][1]=b[3][2]=b[3][3]=1; n=read(); n--; while(n) { if(n&1)mul(a,b,a); mul(b,b,b); n>>=1; } ll ans=0; for(int i=1;i<=3;i++) ans=(ans+a[i][1])%mod; printf("%d\n",ans); } return 0; } |
计数器 9787077
OI 课件=>
OI 课件=>
分段打表才是王道
orz学长
是强啊