BZOJ4002【JLOI2015】有意义的字符串 <线性齐次递推>

Problem

【JLOI2015】有意义的字符串

Description

有两个好朋友，他们叫宁宁和冉冉。
有一天，冉冉遇到了一个有趣的题目：输入，求

Input

一行三个整数。

Output

一行一个数表示模之后的结果。

Sample Input

1 5 9

Sample Output

Hint

，，，。

标签：线性齐次递推

Solution

回忆二阶线性齐次递推的通项形式。

对于线性递推，其特征方程为，设其两根为。则通项的形式为，其中为可根据特解计算的待定系数。
可以构造一个序列，使得其通项为，那么其特征方程的两根为。于是可以还原其递推式，得到

由于，可知，为整数。可以构造转移矩阵，用矩阵快速幂计算。

接下来考虑如何根据计算答案。
由，可知。于是当时，，有；否则，有。

综上，在矩阵快速幂后根据的奇偶性调整答案即可。

Code

#include <bits/stdc++.h>
#define P 7528443412579576937
using namespace std;
typedef long long lnt;
typedef unsigned long long unt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt n, b, d;
lnt add(lnt x, lnt y) {
    unt s = (unt)x+(unt)y;
    return (lnt)(s%P);
}
lnt mul(lnt x, lnt y) {
    lnt ret = 0; if (x < y) swap(x, y);
    for (; y; x = add(x, x)%P, y >>= 1)
        if (y&1) ret = add(ret, x)%P;
    return ret;
}
struct Matrix {
    lnt ele[2][2];
    Matrix () {memset(ele, 0, sizeof ele);}
    inline Matrix operator * (const Matrix &x) const {
        Matrix ret;
        for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++)
            ret.ele[i][j] = add(ret.ele[i][j], mul(ele[i][k], x.ele[k][j]))%P;
        return ret;
    }
} a, m;
Matrix Power(Matrix mat, lnt k) {
    Matrix ret;
    ret.ele[0][0] = 1;
    ret.ele[1][1] = 1;
    for (; k; k >>= 1, mat = mat*mat)
        if (k&1) ret = ret*mat;
    return ret;
}
int main() {
    read(b), read(d), read(n);
    if (!n) return puts("1"), 0;
    a.ele[0][0] = b, a.ele[0][1] = 2;
    m.ele[0][0] = b, m.ele[0][1] = 1;
    m.ele[1][0] = P-((mul(b, b)-d)>>2);
    a = a*Power(m, n-1), a.ele[0][0] -= !(n&1);
    return printf("%lld\n", a.ele[0][0]), 0;
}