acm-递推求值

发布时间:2014-10-23 23:24:52
来源:分享查询网

递推求值 时间限制:1000 ms  |  内存限制:65535 KB 难度:4 描述 给你一个递推公式: f(x)=a*f(x-2)+b*f(x-1)+c 并给你f(1),f(2)的值,请求出f(n)的值,由于f(n)的值可能过大,求出f(n)对1000007取模后的值。 注意:-1对3取模后等于2 输入 第一行是一个整数T,表示测试数据的组数(T<=10000) 随后每行有六个整数,分别表示f(1),f(2),a,b,c,n的值。 其中0<=f(1),f(2)<100,-100<=a,b,c<=100,1<=n<=100000000 (10^9) 输出 输出f(n)对1000007取模后的值 样例输入 2 1 1 1 1 0 5 1 1 -1 -10 -100 3 样例输出 5 999896 来源 经典题目 代码: #include<stdio.h> #include<iostream> #include<string.h> #define max 1000007 typedef struct numb {  long long a[3][3];   }numb; numb arry; numb test; void mult(numb &x,numb y,numb z) {  memset(x.a,0,sizeof(x.a));  for(int i=0;i<3;i++)   for(int j=0;j<3;j++)   {    x.a[i][j]=0;    for(int s=0;s<3;s++)    {     x.a[i][j]+=y.a[i][s]*z.a[s][j];    }      x.a[i][j]%=max;   } } int main() {  int t;  scanf("%d",&t);  while(t--)  {   int f1,f2,a,b,c,n;   scanf("%d%d%d%d%d%d",&f1,&f2,&a,&b,&c,&n);   if(n==1)   {    printf("%d\n",f1);    }   else if(n==2)   {    printf("%d\n",f2);   }   else   {    memset(arry.a,0,sizeof(arry.a));//原矩阵    arry.a[0][0]=f1;    arry.a[0][1]=f2;    arry.a[0][2]=c;        memset(test.a,0,sizeof(test.a));//中间矩阵    test.a[0][1]=a;    test.a[1][0]=1;    test.a[1][1]=b;    test.a[2][1]=1;    test.a[2][2]=1;    n-=2;    numb tmp;    memset(tmp.a,0,sizeof(tmp.a));      for(int i=0;i<3;i++)     tmp.a[i][i]=1;    while(n)    {     if(n&1)      mult(tmp,tmp,test);     n>>=1;     mult(test,test,test);     }    mult(arry,arry,tmp);    if(arry.a[0][1]>0)     printf("%d\n",arry.a[0][1]);    else printf("%d\n",arry.a[0][1]+max);   }   }  return 0; }

返回顶部
查看电脑版