【UVA-10655】Contemplation! Algebra【矩阵快速幂】

【UVA-10655】Contemplation! Algebra【矩阵快速幂】

问题链接:https://vjudge.net/problem/UVA-10655

Solution:

在纸上尝试一下,发现:

\((a + b)(a + b) – 2ab = a^2 + b^2\)

\((a^2 + b^2)(a + b) – (a + b)ab = a^3 + b^3\)

\((a^3 + b^3)(a + b) – (a^2 + b^2)ab = a^4 + b^4\)

……

转移方式是固定的,我们可以写出矩阵变换式:

\((^{a^n + b^n}_{a^{n – 1} + b^{n – 1}}) = (^{a + b}_1\)      \(^{-ab}_0) ^{n – 1}(^{a + b}_{2})\)

根据这个写矩阵快速幂就好。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
const int LIM = 2;
struct Matrix {
    LL v[LIM][LIM];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        for (int i = 0; i < LIM; i++) {
            for (int k = 0; k < LIM; k++) {
                if (v[i][k])
                    for (int j = 0; j < LIM; j++) {
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]);
                    }
            }
        }
        return ret;
    }
};
// p = a + b, q = ab
LL p, q, n;
Matrix base;

void build() {
    base.v[0][0] = p;
    base.v[0][1] = -q;
    base.v[1][0] = 1;
    base.v[1][1] = 0;
}

Matrix fastPow(LL p, Matrix m) {
    Matrix ret = {0};
    for(int i = 0; i < LIM; i++) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret = ret * m;
        if (p) m = m * m;
        p >>= 1;
    }
    return ret;
}

int main() {
    while (scanf("%lld%lld%lld", &p, &q, &n) == 3 && (p || q || n)) {
        if (n == 0) printf("2\n");
        else if (n == 1) printf("%lld\n", p);
        else {
            build();
            Matrix trans = fastPow(n - 1, base);
            printf("%lld\n", trans.v[0][0] * p + trans.v[0][1] * 2);
        }
    }
    return 0;
}

 

【UVA-11149】Power of Matrix【矩阵快速幂】

【UVA-11149】Power of Matrix【矩阵快速幂】

问题链接:https://vjudge.net/problem/UVA-11149

Solution:

二分,对于偶数k,表达式

\(A + A^2 + A^3 + … + A^k = (A + A^2 + … + A^{k / 2})(E + A^{k / 2})\)

当k是奇数的时候,上式k / 2向下取整,并且上式在右侧补加\(A ^ k\)项。

递归处理就好。

需要注意的是,n = 0结束,不一定会有k = 0输入。

输入不一定只有一位,要对输入先取模,不然会WA。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int MOD = 10;
const int LIM = 40 + 10;
struct Matrix {
    int v[LIM][LIM];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}};
        ret.size = size;
        for (int i = 0; i < size; i++) {
            for (int k = 0; k < size; k++) {
                if (v[i][k])
                    for (int j = 0; j < size; j++) {
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
                    }
            }
        }
        return ret;
    }
    Matrix operator + (const Matrix & m) const {
        Matrix ret = {{0}};
        ret.size = size;
        for (int i = 0; i < size; i++)
            for (int j = 0; j < size; j++)
                ret.v[i][j] = (v[i][j] + m.v[i][j]) % MOD;
        return ret;
    }
};
int n;
Matrix iden, base;

inline void init() {
    memset(&iden, 0, sizeof iden);
    for (int i = 0; i < n; i++) iden.v[i][i] = 1;
    iden.size = n;
    memset(&base, 0, sizeof base);
    base.size = n;
}

Matrix fastPow(int p, Matrix m) {
    Matrix ret = {{0}};
    ret.size = m.size;
    for(int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret = ret * m;
        if (p) m = m * m;
        p >>= 1;
    }
    return ret;
}

Matrix binarySum(int k) {
    if (k == 1) return base;
    else if (k & 1) return binarySum(k >> 1) * (iden + fastPow(k >> 1, base)) + fastPow(k, base);
    else return binarySum(k >> 1) * (iden + fastPow(k >> 1, base));
}

int main() {
    int k;
    while (~scanf("%d", &n) && n) {
        scanf("%d", &k);
        init();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                scanf("%d", &base.v[i][j]);
                base.v[i][j] %= MOD;
            }
        Matrix ans = binarySum(k);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j) putchar(' ');
                printf("%d", ans.v[i][j]);
            }
            putchar('\n');
        }
        putchar('\n');
    }
    return 0;
}

 

【UVA – 10689】Yet another Number Sequence

【UVA – 10689】Yet another Number Sequence

问题链接:https://vjudge.net/problem/UVA-10689

Solution:

em…不用多想,就是个用矩阵快速幂求第n项。

唯一需要注意的是Output那里有说取模的事情。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int MOD = 0;
const int LIM = 2;
struct Matrix {
    int v[LIM][LIM];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        for (int i = 0; i < LIM; i++) {
            for (int k = 0; k < LIM; k++) {
                if (v[i][k])
                    for (int j = 0; j < LIM; j++) {
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
                    }
            }
        }
        return ret;
    }
};

const Matrix BASE = {1, 1, 1, 0};

Matrix fastPow(int p, Matrix m) {
    Matrix ret = {0};
    for(int i = 0; i < LIM; i++) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret = ret * m;
        if (p) m = m * m;
        p >>= 1;
    }
    return ret;
}

int main() {
    int t;
    scanf("%d",&t);
    int a, b, n, m;
    while (t--) {
        scanf("%d%d%d%d", &a, &b, &n, &m);
        MOD = 1;
        while (m--) MOD *= 10;
        if (n == 0) printf("%d\n", a);
        else if (n == 1) printf("%d\n", b);
        else {
            Matrix trans = fastPow(n - 1, BASE);
            printf("%d\n", (b * trans.v[0][0] + a * trans.v[0][1]) % MOD);
        }
    }
    return 0;
}

 

【UVA-11551】Experienced Endeavour【矩阵快速幂】

【UVA-11551】Experienced Endeavour【矩阵快速幂】

问题链接:https://vjudge.net/problem/UVA-11551

Solution:

根据题目要求构造一个变换矩阵,然后进行矩阵快速幂就好,注意别忘记取模。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int MOD = 1000;
const int LIM = 50 + 10;
struct Matrix {
    int v[LIM][LIM];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}};
        ret.size = size;
        for (int i = 0; i < size; i++) {
            for (int k = 0; k < size; k++) {
                if (v[i][k])
                    for (int j = 0; j < size; j++) {
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
                    }
            }
        }
        return ret;
    }
};
int a[LIM], ans[LIM], n;

inline void init() {
    memset(ans, 0, sizeof ans);
}

Matrix fastPow(int p, Matrix m) {
    Matrix ret = {{0}};
    ret.size = m.size;
    for(int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret = ret * m;
        if (p) m = m * m;
        p >>= 1;
    }
    return ret;
}

int main() {
    int t;
    scanf("%d",&t);
    int r, x, b;
    while (t--) {
        init();
        scanf("%d%d", &n, &r);
        for(int i = 0; i < n; i++) scanf("%d", &a[i]);
        Matrix base = {{0}};
        base.size = n;
        for(int i = 0 ; i < n; i++) {
            scanf("%d", &x);
            for(int j = 0 ; j < x; j++) {
                scanf("%d", &b);
                base.v[i][b] = 1;
            }
        }
        base = fastPow(r, base);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                ans[i] = (ans[i] + a[j] * base.v[i][j]) % MOD;
        for(int i = 0; i < n; i++) {
            if (i) putchar(' ');
            printf("%d", ans[i]);
        }
        putchar('\n');
    }
    return 0;
}

 

【HDU-4965】Fast Matrix Calculation

【HDU-4965】Fast Matrix Calculation

矩阵乘法结合律的应用

问题链接:https://vjudge.net/problem/HDU-4965

Solution:

计算\((A B) ^{n * n}\),由于AB是n * n矩阵,而BA是k * k矩阵,其中n最大值1000,k最大值6,显然需要将上式改成\(A (BA)^{n * n – 1}B\),中间的部分用矩阵快速幂来算。

如果开1000 * 1000的long long矩阵,在全局作用域下声明多个这样的对象,程序最后可能产生与数组开太同样的问题。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000 + 10;
const int K = 6 + 2;
const int MOD = 6;
struct Matrix {
    int v[K][K];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}};
        ret.size = size;
        for (int i = 0; i < size; i++) {
            for (int k = 0; k < size; k++) {
                if (v[i][k]) {
                    for (int j = 0; j < size; j++) {
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
                    }
                }
            }
        }
        return ret;
    }
} c;
int a[N][K], b[K][N];
long long tmp[N][K], ans[N][N];
int n, k;

Matrix build() {
    Matrix ret = {{0}};
    ret.size = k;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            for (int w = 0; w < n; w++) {
                ret.v[i][j] = (ret.v[i][j] + b[i][w] * a[w][j]) % MOD;
            }
        }
    }
    return ret;
}

Matrix powMod(int p, Matrix m) {
    Matrix ret = {{0}};
    ret.size = m.size;
    for (int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret = m * ret;
        if (p) m = m * m;
        p >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    while (cin >> n >> k && n && k) {
        memset(tmp, 0, sizeof tmp);
        memset(ans, 0, sizeof ans);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < k; j++)
                cin >> a[i][j];
        for (int i = 0; i < k; i++)
            for (int j = 0; j < n; j++)
                cin >> b[i][j];
        Matrix c = build();
        c = powMod(n * n - 1, c);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                for (int w = 0; w < k; w++) {
                    tmp[i][j] = (tmp[i][j] + a[i][w] * c.v[w][j]) % MOD;
                }
            }
        }
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int w = 0; w < k; w++) {
                    ans[i][j] = (ans[i][j] + tmp[i][w] * b[w][j]) % MOD;
                }
                sum += ans[i][j];
            }
        }
        cout << sum << endl;
    }
    return 0;
}

 

【UVA-11651】Krypton Number System

【UVA-11651】Krypton Number System

通过矩阵快速幂转移状态

问题链接:https://vjudge.net/problem/UVA-11651

Solution:

首先关注到,对于每一种数字组合,可以都可以对应到一种确定的score值,而每一个score可以由多种数组组合得到。

最简单的考虑,自然是枚举数字组合,也就是搜索的办法,由于两个相邻数最小间隔为1,所以这个数字组合最长可能是S+1长度的,每个位置有B种选择,所以枚举的复杂度是\(O(TB^S)\)【其中T是数据组数】。这样显然无法在规定时间内跑完。

于是,我们从另一个角度——score的方面来考虑,注意到对于每一个score值,它的结尾数字只有B种,而转移到下一个score值仅与上一个score值相关,只需要对于每一种结尾枚举其下一个可能结尾就好,那么显然有:

\(dp[i][k] = \sum dp[i – (j – k)^2][j]\)

我们就可以使用动态规划来解决这个问题,对于每一个score值,我们需要枚举其B种结尾,对于每一种结尾,我们枚举下一个可能的结尾进行转移,因此复杂度是\(O(TSB^2)\)。十分可惜的是,这样依旧会TLE,还需要进一步优化。

这时注意到,对于单次转移,最远只能从第i行转移到\(i+(b – 1)^2\)行,也就是说,转移的方式是固定的,如果将dp数组的前\((b – 1)^2 – 1\)行构造成一个一维向量【把二维数组中的元素从左到右,从上到下依次排下来就好】,我们就可以通过写出一个\((b- 1) ^ 2 * b\)转移矩阵,得到任意位置的dp数组数据,具体点来说,如果对0到\((b – 1)^2 – 1\)dp数据乘一次转移矩阵,就得到1到\((b – 2)^2\)的dp数据。我们使用矩阵快速幂来先对变换矩阵进行计算。复杂度\(O(TB^9logS)\),虽然其中B的次数增高了,但是本题中数值很大的S变成了logS。

另外,由于转移矩阵十分稀疏【中间存在很多0】,我们需要调整一下矩阵乘法的顺序,并且先判断其中一边的值是否为0,再决定是否要相乘,可以节省很多时间。

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;
const LL MOD = 1ll << 32;
const int LIM = 250;
struct Matrix {
    LL v[LIM][LIM];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        ret.size = size;
        for (int i = 0; i < size; i++) {
            for (int k = 0; k < size; k++) {
                if (v[i][k]) {
                    for (int j = 0; j < size; j++) {
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
                    }
                }
            }
        }
        return ret;
    }
};
int b;
LL s, ans;
LL dp[LIM][LIM];

inline void init() {
    memset(dp, 0, sizeof dp);
    ans = 0;
    int lim = (b - 1) * (b - 1);
    for (int j = 1; j < b; j++) dp[0][j] = 1;
    for (int i = 0; i <= lim; i++) {
        for (int j = 0; j < b; j++) {
            for (int k = 0; k < b; k++) {
                if (j == k) continue;
                int tmp = (j - k) * (j - k);
                if (i + tmp > lim) continue;
                dp[i + tmp][k] += dp[i][j];
            }
        }
    }
}

Matrix buildBase() {
    Matrix ret = {{0}};
    ret.size = (b - 1) * (b - 1) * b;
    LL tmp;
    for (int i = 0; i <= ret.size - b; i++)
        ret.v[i][i + b] = 1;
    int lim = (b - 1) * (b - 1);
    for (int i = 0; i < lim; i++) {
        for (int j = 0; j < b; j++) {
            for (int k = 0; k < b; k++) {
                if (j == k) continue;
                tmp = i + (k - j) * (k - j);
                if (tmp == lim) ret.v[(tmp - 1) * b + k][i * b + j] = 1;
            }
        }
    }
    return ret;
}

Matrix powMod(int pow, Matrix m) {
    Matrix ret = {{0}};
    ret.size = m.size;
    for (int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
    while (pow) {
        if (pow & 1) {
            ret = m * ret;
        }
        if (pow) m = m * m;
        pow >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    for (int k = 1; k <= t; k++) {
        cin >> b >> s;
        init();
        int lim = (b - 1) * (b - 1);
        if (s <= lim) {
            for (int j = 0; j < b; j++) ans += dp[s][j];
            cout << "Case " << k << ": " << ans << "\n";
        } else {
            Matrix base = buildBase();
            int size = lim * b;
            int pos = (lim - 1) * b;
            base = powMod(s - lim, base);
            for (int j = 0; j < b; j++) {
                LL tmp = 0;
                for (int k = 0; k < size; k++)
                    tmp = (tmp + base.v[pos + j][k] * dp[k / b + 1][k % b]) % MOD;
                ans = (ans + tmp + MOD) % MOD;
            }
            cout << "Case " << k << ": " << ans << "\n";
        }
    }
    return 0;
}

 

【HDU-4990】Reading comprehension

【HDU-4990】Reading comprehension

Solution:

看上去是分奇偶的,但是具有统一的递推形式:

记\(a_k\)为第k项的值。

Part 1.当k是偶数时,则\(a_k = a_{k – 1} \times 2 = a_{k – 1} + 2 \times a_{k – 2} + 1\)。

Part 2.当k是奇数时,则\(a_k = a_{k – 1} \times 2 +1 = a_{k – 1} + 2 \times a_{k – 1} + 1\)。

写出变换矩阵就可以解决了。

#include <iostream>

using namespace std;

typedef long long LL;
LL MOD;
struct Matrix {
    LL t[3][3];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    ret.t[i][j] = (ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD;
                }
            }
        }
        return ret;
    }
};

const Matrix BASE = {{1, 2, 1, 1, 0, 0, 0, 0, 1}};

Matrix powMod(int pow, Matrix m) {
    Matrix ret = {{1, 0, 0, 0, 1, 0, 0, 0, 1}};
    while (pow) {
        if (pow & 1) ret = ret * m;
        m = m * m;
        pow >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n;
    while (cin >> n >> MOD) {
        if (n == 1) cout << 1 % MOD << "\n";
        else if (n == 2) cout << 2 % MOD << "\n";
        else {
            Matrix trans = powMod(n - 2, BASE);
            LL ans = (trans.t[0][0] * 2 + trans.t[0][1] * 1 + trans.t[0][2]) % MOD;
            cout << ans << "\n";
        }
    }
    return 0;
}

 

 

【HDU-5015】233 Matrix【矩阵快速幂】

【HDU-5015】233 Matrix【矩阵快速幂】

Solution:

看到这道题,最先想说233333…

最先考虑到的方法,当然是直接暴力推,反正每个位置只与它左侧及上侧有关,推到要求的那个位置上就好,但是这样单组数据复杂度是\(O(nm)\),虽然有5000ms,但是一般这种题目数据量会很大,这样暴力绝对会超时,于是考虑到需要更快的迭代方法,第一列依次是\(0, a_1, a_2… a_n\),尝试在纸上把这个矩阵列出来,并且把每个位置上的值都只使用这些已知符号代替,我们发现一个规律,每个位置上的数实际上都把这一列它上方的所有数都加了进来,同理也把它左边的所有数都加了进来,进行简单的整理后,我们发现:每一行可以仅由上一行的值推出,每一列也可以仅由上一列的值推出。由上一行推的时候需要考虑到一个与输入相关的无规律常数,这个常数的存在破坏了递推形式不变性,所以只能够用刚才\(O(nm)\)复杂度的方法推;而由上一列推这一列时,我们需要考虑一个题目中拟定的嘲讽一般的233,它的规律很明显,由上一列到这一列,它的值扩10倍后加3便可完成这次递推,唯一不满足的就是最前面那一列的0。这时,注意到,在整个矩阵中,左上角的0是唯一一个不对结果产生贡献的值(并不是因为它是0,而是因为根据题设递推规则,它没有被加入到\(a_{nm}\)中),这样,它的值可以任意修改,那么我们便修改成23,这时每一列之间的递推形式固定的了下来,可以写出变换矩阵,之后使用矩阵快速幂来求解,复杂度降到\(O(n^3logm)\)。

总结一下,这道题关键是:

1.发现可以通过每一列的值推出下一列的值。

2.注意到0没有贡献于最终结果,是题设故意设计的一个坑。

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 10000007;
const int LIM = 15;
struct Matrix {
    LL t[LIM][LIM];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}, size};
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    ret.t[i][j] = (ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD;
                }
            }
        }
        return ret;
    }
};

Matrix buildBase(int size) {
    Matrix ret = {{0}, size};
    ret.t[size - 1][size - 1] = 1;
    for (int i = size - 2; i >= 0; i--) {
        ret.t[i][0] = 10;
        ret.t[i][size - 1] = 1;
        for (int j = 1; j <= i; j++)
            ret.t[i][j] = 1;
    }
    return ret;
}

Matrix powMod(int pow, Matrix m) {
    Matrix ret = {{0}, m.size};
    for (int i = 0; i < ret.size; i++)
        ret.t[i][i] = 1;
    while (pow) {
        if (pow & 1) ret = ret * m;
        m = m * m;
        pow >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n, m;
    LL ori[LIM];
    while (cin >> n >> m) {
        ori[0] = 23;
        ori[n + 1] = 3;
        for (int i = 1; i <= n; i++) cin >> ori[i];
        if (m == 0) cout << ori[n] << "\n";
        else {
            Matrix trans = powMod(m, buildBase(n + 2));
            LL ans = 0;
            for (int i = 0; i <= n + 1; i++)
                ans = (ans + trans.t[n][i] * ori[i]) % MOD;
            cout << ans << "\n";
        }
    }
    return 0;
}

 

【CodeForces-450B】Jzzhu and Sequences【矩阵快速幂】

【CodeForces-450B】Jzzhu and Sequences【矩阵快速幂】

Solution:

涉及到负数的取模运算,根据算法的不同结果是不一样的,推荐一篇博客:https://blog.csdn.net/hk2291976/article/details/52775299

这道题的操作是只在最后结果的时候如果是负数就把它变成正的,结果等价于上面链接博客中的第二种方法。【本段已删除】

后来突然想到了问题,是自己取模顺序搞错了,结果一直WA,对于负数取模,如果要求结果必须正的话,处理方法形如((a % MOD) + MOD) % MOD。

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 1e9 + 7;
struct Matrix {
    LL t[2][2];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    ret.t[i][j] = ((ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD + MOD) % MOD;
                }
            }
        }
        return ret;
    }
};

const Matrix BASE = {{1, -1, 1, 0}};

Matrix powMod(int pow, Matrix m) {
    Matrix ret = {{1, 0, 0, 1}};
    while (pow) {
        if (pow & 1) ret = ret * m;
        m = m * m;
        pow >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL x, y, n;
    while (cin >> x >> y >> n) {
        if (n == 1) cout << (x + MOD) % MOD << "\n";
        else if (n == 2) cout << (y + MOD) % MOD << "\n";
        else {
            Matrix trans = powMod(n - 2, BASE);
            cout << ((trans.t[0][0] * y + trans.t[0][1] * x) % MOD + MOD) % MOD << "\n";
        }
    }
    return 0;
}