人类史上最大最好的希望事件 字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛

作为CNCS的半壁*，狗哥常常在宇宙中心邵阳眺望黄浦江，夜晚的星空总是迷人，有时候还能见到彗星滑落。

狗哥是幸运的，他在两秒钟内看到了十七颗彗星划过天际，作为打ACM的学者，自然不会有「稳定-1」情况。他开始研究彗星运动的轨迹，发现他们都遵照斐波那契螺旋线在运动着。

尤里卡！狗哥觉得这就是找寻「生命，宇宙和一切的终极答案」的精要所在，但是怎么表示呢？狗哥觉得求取斐波那契螺旋线经过的一个个方格的面积之和就是公式的表现。

例如下图，螺旋线每划过一个方格，都转过了四分之一圈。如果我们以四分之一圈为单位，那么我们用类似带分数的形式表示螺旋线转动的起点和终点。例如，0+0 到 0 + 1 意即从第一个方格转到第二个方格，划过了前两个方格，他们的面积之和为2（1+1）。同理，0+0 到 1+0 划过了前五个方格，他们的面积之和为40（1+1+4+9+25）。
 

但是聪明的狗哥需要一个程序去获得指定范围内的螺旋线面积之和，狗哥给了你一首「希望之花」的时间，而他需要利用这个时间去打出四暗刻单骑。如果你能完成这个程序，狗哥会封你为格拉摩根伯爵

 

 

Input

不定组数据。

首先输入一个整数Q，代表狗哥询问次数。

接下来Q行，每行四个整数a,b,c,d，代表狗哥想求 a+b 到 c+d 之间的螺旋线面积之和。

1<= Q <= 10000

0<= a,c <= 10000

0 <= b,d <= 3

结果对192600817取模。

 

 

Output

一个数字，表示螺旋线面积之和。

Sample Input
4
0 0 0 1
0 0 1 0
1 2 2 1
1 1 0 3
4
0 0 0 1
0 0 1 0
1 2 2 1
1 1 0 3
 

Sample Output
2
40
4791
98
2
40
4791
98

思路：每个位置的值都是斐波那契数列的平方，输入a,b,c,d;那么将a 作为4*a,c 作为4*c 那么初始就为4*a+b+1, 到 4*c+d+1;

预处理一下就好了，由于我先做的最后一题打出来了矩阵快速幂的模板，所以我是用矩阵快速幂做的 ，其实完全没必要。

 

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=192600817;
vector <ll>vec;
struct Marx
{
    ll a[2][2];
}f,it,base;
Marx mul(Marx x,Marx y)
{
    Marx ret;
    memset(ret.a,0,sizeof(ret.a));
    for(int i=0;i<2;i++)
    {
        for(int k=0;k<2;k++)
        {
            for(int j=0;j<2;j++)
            {
                ret.a[i][j]=(ret.a[i][j]+(x.a[i][k]*y.a[k][j])%mod)%mod;
            }
        }
    }
    return ret;
}
Marx ksm(ll n)
{
    if(!n)return it;
    Marx tmp=ksm(n>>1);
    if(n&1)return mul(mul(tmp,tmp),base);
    return mul(tmp,tmp);
}
void init()
{
    base.a[0][0]=base.a[0][1]=base.a[1][0]=1;
    it.a[0][0]=it.a[1][1]=1;
    f.a[0][0]=f.a[1][0]=1;
    int y=2;
    Marx kk;
    vec.push_back(0);
    vec.push_back(1);
    vec.push_back(2);
    memset(kk.a,0,sizeof(kk.a));
    for(int i=3;i<=50005;i++)
    {
        kk=mul(ksm(i-2),f);
        ll ans=kk.a[0][0];
        ans=((ans%mod*ans%mod)%mod+vec[i-1])%mod;
        vec.push_back(ans);
    }
}
int main()
{
    int t;
    init();
    while(scanf("%d",&t)!=EOF)
    {
        while(t--)
        {
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
              int x1=a*4+b+1;
              int x2=c*4+d+1;
              if(x1>x2)swap(x1,x2);
              ll ans=0;
              printf("%lld\n",(vec[x2]-vec[x1-1]+mod)%mod);
        }
    }
    return 0;
}