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

Posted on Symbols count in article: 726 Reading time ≈ 3 mins.

Problem

【JLOI2015】有意义的字符串

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

B君\mathrm{B君}有两个好朋友，他们叫宁宁和冉冉。
有一天，冉冉遇到了一个有趣的题目：输入b,d,nb,d,n，求

⌊(b+d2)n⌋mod  7528443412579576937\lfloor(\frac{b+\sqrt{d}}{2})^n\rfloor\mod{7528443412579576937}

Input

一行三个整数b,d,nb,d,n。

Output

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

Sample Input

1
1 5 9

Sample Output

1
76

Hint

0<b2≤d<(b+1)2≤10180<b^2\le d<(b+1)^2\le10^{18}，n≤1018n\le10^{18}，b≡1 mod 2b\equiv1\bmod{2}，d≡1 mod 4d\equiv1\bmod{4}。

标签：线性齐次递推

Solution

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

对于线性递推Aai+Bai−1+C=0Aa_i+Ba_{i-1}+C=0，其特征方程为Ax2+Bx+C=0Ax^2+Bx+C=0，设其两根为α,β\alpha,\beta。则通项的形式为ai=Pαi+Qβia_i=P\alpha^i+Q\beta^i，其中P,QP,Q为可根据特解计算的待定系数。
可以构造一个序列{ai}\lbrace a_i\rbrace，使得其通项为ai=(b+d2)i+(b−d2)ia_i=(\frac{b+\sqrt{d}}{2})^i+(\frac{b-\sqrt{d}}{2})^i，那么其特征方程的两根为α=b+d2,β=b−d2\alpha=\frac{b+\sqrt{d}}{2},\beta=\frac{b-\sqrt{d}}{2}。于是可以还原其递推式，得到

ai−bai−1+b2−d4=0a0=2,  a1=b,  an=ban−1−b2−d4an−2a_i-ba_{i-1}+\frac{b^2-d}{4}=0\\ a_0=2,\;a_1=b,\;a_n=ba_{n-1}-\frac{b^2-d}{4}a_{n-2}\\

由于b≡1 mod 2,  d≡1 mod 4b\equiv1\bmod{2},\;d\equiv1\bmod{4}，可知4∣b2−d4|b^2-d，b2−d4\frac{b^2-d}{4}为整数。可以构造转移矩阵，用矩阵快速幂计算ana_n。

(an−1an−2)×(b1−b2−d40)=(anan−1)\begin{pmatrix} a_{n-1}&a_{n-2} \end{pmatrix} \times \begin{pmatrix} b&1\\ -\frac{b^2-d}{4}&0 \end{pmatrix} =\begin{pmatrix} a_n&a_{n-1} \end{pmatrix}

接下来考虑如何根据aia_i计算答案。
由0<b2≤d<(b+1)20<b^2\le d<(b+1)^2，可知b−d2∈(−12,0]\frac{b-\sqrt{d}}{2}\in(-\frac{1}{2},0]。于是当2∣n2|n时，(b−d2)n∈[0,12)(\frac{b-\sqrt{d}}{2})^n\in[0,\frac{1}{2})，有Ans=an−1Ans=a_n-1；否则(b−d2)n∈(−12,0](\frac{b-\sqrt{d}}{2})^n\in(-\frac{1}{2},0]，有Ans=anAns=a_n。

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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;
}