NOIP暑期七天营-普及组5-D小w的Fibonacci数列

题目大意：从第三项开始，每一项等于前两项之和，已知第x项和第y项的值，输出第1项和第2项。

类似于斐波拉契数列，第一项是a，第二项是b，那么之后每一项都与a和b有关：

从第1项开始，a的数量是：1 0 1 1 2 3 5 8 13……
从第1项开始，b的数量是：0 1 1 2 3 5 8 13 21……

首先算出第x项有xa个a、xb个b，第y项有ya个a，yb个b。（需要用矩阵快速幂）

xa * a + xb * b = sx（第x项的值）
ya * a + yb * b = sy（第y项的值）

第一个式子乘以ya，第二个式子乘以xa，就可以消去a，算出b了！
b = (sy - sx) / (by - bx);
a = (sx - bx*b) / ax;

在同余情况下，我们可以将除法转换成乘逆元。（需要用到逆元，可以用扩展欧几里德）

注意：翻倍后再乘就容易爆long long，相减也可能出现负数，多取几次模即可。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL n, m, p, i, j, k, s, ansa, ansb;
LL x, y, sx, sy, ax, bx, ay, by, xx, yy;
LL a[55][55], b[55][55], c[55][55];
void cheng(LL a[][55], LL b[][55], LL c[][55]){
    LL i, j, k;
    for(i=1; i<=2; i++){
        for(j=1; j<=2; j++){
            c[i][j] = 0;
            for(k=1; k<=2; k++){
                c[i][j] += a[i][k] * b[k][j];
                c[i][j] %= p;
            }
        }
    }
}
LL fn(LL n){
    m = n - 2, p = 1e9 + 7;
    a[1][1] = a[1][2] = a[2][1] = 1;
    c[1][1] = c[2][2] = 1;
    a[2][2] = c[1][2] = c[2][1] = 0;
    for(i=0; i<32 && m>0; i++){
        if(m & (1<<i)){
            memcpy(b, c, sizeof(b));
            cheng(a, b, c);
            m ^= 1 << i;
        }
        memcpy(b, a, sizeof(b));
        cheng(b, b, a);
    }
    if(n == 0) return 0;
    else if(n <= 2) return 1;
    else return (c[1][1] + c[1][2]) % p;
}
void exgcd(LL a, LL b, LL &x, LL &y){
    if(b == 0) x = 1, y = 0;
    else{
        exgcd(b, a%b, y, x);
        y -= a/b * x;
    }
}
int main(){
    scanf("%lld%lld%lld%lld", &x, &sx, &y, &sy);
    xx = ax = x<3 ? (x&1) : fn(x-2);
    yy = ay = y<3 ? (y&1) : fn(y-2);
    bx = x<2 ? 0 : fn(x-1);
    by = y<2 ? 0 : fn(y-1);
    ax *= yy, bx *= yy, sx *= yy;
    ay *= xx, by *= xx, sy *= xx;
//    ansb = (sy - sx) / (by - bx);
    exgcd((by-bx)%p+p, p, x, y);
    x = x%p + p;
    ansb = (sy - sx) % p * x % p + p;
//    ansa = (sx - bx*ansb) / ax;
    exgcd(ax%p+p, p, x, y);
    x = x%p + p;
    ansa = ((sx - bx%p*ansb) % p + p) * x % p + p;
    printf("%lld %lld\n", x=ansa%p, y=ansb%p);
    return 0;
}