【牛客NOIP暑期七天营-普及组5】小w的Fibonacci数列

题目描述

小w有一个神奇的数列，它满足Fibonacci数列的递推公式。即 $F [i] = F [i - 1] + F [i - 2]$ ，但是小w手中的数列前两项与Fibonacci数列不同。也就是说小w数列是这样定义的：

$F [1] = A;$

$F [2] = B;$

$F [i] = F [i - 1] + F [i - 2]; (i > 2)$

小w不小心忘记了他定义的 $A$ 与 $B$ 是多少了，但是好在他还记得其中的第 $x$ 项的值为 $v a l x$ ，第y项的值为 $v a l y$ 。

为了避免这两个数字过大，他告诉你这两个数字 $m o d 1 0^{9} + 7$ 后的值是多少。
输入数据保证模条件下存在 $A$ $B$ 使得 $F [x] = v a l x$ 且 $F [y] = v a l y$ 成立。
请输出任意一组可行的 $A$ 和 $B$ 。

输入描述:

一行四个整数 $x$ , $v a l x$ , $y$ , $v a l y$ 。且保证至少有一种合法的解。

输出描述:

对于每组案例，请你输出符合条件的 $A$ $B$ 。
如果有多解，你只需输出任意一种合法解即可。

示例1

输入

5 5 8 21

输出

1 1

说明
小w数列可为
1 1 2 3 5 8 13 21…
满足第5项为5，且第8项为21。

示例2

输入

5 4100 7 10700

输出

700 900

说明
小w数列可为
700 900 1600 2500 4100 6600 10700…
满足第5项为4100，第7项为10700。
备注:

Solution

易知，
$a_{1} A + b_{1} B = c_{1}$
$a_{2} A + b_{2} B = c_{2}$
所以矩阵快速幂+费马小定理乱搞一通即可（太难写了）

#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;

const ll M = 1e9 + 7;

class matrix
{
public:
	ll a[2][2];
	matrix(ll t1, ll t2, ll t3, ll t4)
	{
		a[0][0] = t1; a[0][1] = t2;
		a[1][0] = t3; a[1][1] = t4;
	}
	matrix() {}
	matrix operator * (matrix b)
	{
		matrix res;
		res.a[0][0] = (a[0][0] * b.a[0][0] + a[0][1] * b.a[1][0]) % M;
		res.a[0][1] = (a[0][0] * b.a[0][1] + a[0][1] * b.a[1][1]) % M;
		res.a[1][0] = (a[1][0] * b.a[0][0] + a[1][1] * b.a[1][0]) % M;
		res.a[1][1] = (a[1][0] * b.a[0][1] + a[1][1] * b.a[1][1]) % M;

		return res;
	}
};

matrix pow(matrix a, ll x)
{
	matrix res(1, 0, 0, 1);
	for (; x; x /= 2)
	{
		if (x % 2) res = res * a;
		a = a * a;
	}

	return res;
}

ll ask(ll n)
{
	if (n <= 2)
		return 1;
	matrix a(1, 1, 1, 0);
	matrix p = pow(a, n - 2);
	ll s = (p.a[0][0] + p.a[1][0]) % M;

	return s;
}

ll power(ll a, ll b, ll p)
{
    a %= M;
	ll res(1);
	for (; b; b /= 2)
	{
		if (b % 2) res = (res * a) % p;
		a = (a * a) % p;
	}
	return res;
}

ll x, c1, y, c2;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> x >> c1 >> y >> c2;
	ll a1, b1, a2, b2;
	if (x == 1) a1 = 1, b1 = 0;
	else if (x == 2) a1 = 0, b1 = 1;
	else a1 = ask(x - 2), b1 = ask(x - 1);
	if (y == 1) a2 = 1, b2 = 0;
	else if (y == 2) a2 = 0, b2 = 1;
	else a2 = ask(y - 2), b2 = ask(y - 1);
	ll A1 = a1, A2 = a2;
	a1 *= A2; b1 *= A2; c1 *= A2;
	a2 *= A1; b2 *= A1; c2 *= A1;
	a1 %= M; b1 %= M; c1 %= M;
	a2 %= M; b2 %= M; c2 %= M;
	if (c1 > c2)
	{
		swap(a1, a2);
		swap(b1, b2);
		swap(c1, c2);
	}
	ll Y = (c2 - c1) % M * power(b2 - b1, M - 2, M) % M;
	ll X = (c1 - Y * b1) % M * power(a1, M - 2, M) % M;
	cout << X << ' ' << Y << endl;

	return 0;
}