Subtask ~1~ ~(n \le 6)~.

• Ta sinh tất cả các dãy số độ dài ~n~ và kiểm tra.
• Đpt: ~O(10^n)~

Subtask ~2~ ~(n \le 10^6)~

• Gọi số cách để nhận được tiền polime ở xâu có độ dài ~i~ là ~p_i~, tiền giấy là ~g_i~, ta có công thức quy hoạch động như sau:

\begin{cases} ~p_i = p_{i - 1} \times 5 + g_{i - 1} \times 3~ \\ ~g_i = p_{i - 1} \times 5 + g_{i - 1} \times 7~ \end{cases}

Subtask ~3~ ~(n \le 10^9)~

• Với ~n~ lớn, ta không thể quy hoạch động bằng phép duyệt thông thường. Ta cần chuyển công thức quy hoạch động sang ma trận để thực hiện nhân ma trận.

~[f(0, i - 1), f(1, i - 1)] \times \begin{bmatrix} 5 & 3 \\\ 5 & 7 \end{bmatrix} = [f(0, i), f(1, i)]~

• Từ đây suy ra:

~[f(0, n), f(1, n)] = [f(0, 0), f(1, 0)] \times \begin{bmatrix} 5 & 3 \\\ 5 & 7 \end{bmatrix}^n~

Code tham khảo

#include <bits/stdc++.h>
#define BIT(x, i) (((x) >> (i))&1)
#define MASK(i) (1ll<<(i))
#define all(x) x.begin(), x.end()
#define reu(i, a, b) for(int i = (a); i <= (b); ++i)
#define red(i, a, b) for(int i = (a); i >= (b); --i)
#define F first
#define S second
#define pb push_back
using namespace std;

typedef long long ll;

const int N = 1e5 + 2;
const ll mod = 1e9 + 7;

ll n;

struct matrix {
    ll data[2][2];
    matrix operator*(const matrix &A) {
        matrix res;
        memset(res.data, 0, sizeof res.data);
        reu(i, 0, 1) reu(j, 0, 1) reu(k, 0, 1)
            res.data[i][j] = (res.data[i][j] + data[i][k] * A.data[k][j] % mod) % mod;
        return res;
    }
};

matrix Pow(matrix base, ll i) {
    matrix ans;
    ans.data[0][0] = ans.data[1][0] = 1;
    ans.data[0][1] = ans.data[1][1] = 0;
    for(; i; i >>= 1, base = base * base)
        if (i & 1) ans = ans * base;
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n;
    matrix a;
    a.data[0][0] = 5; a.data[0][1] = 3;
    a.data[1][0] = 5; a.data[1][1] = 7;
    a = Pow(a, n);
    cout << a.data[0][0];

    return 0;
}