TIOJ-2021

2qbingxuan

2019-12-04

F.無限兔子問題

https://tioj.ck.tp.edu.tw/problems/2021

Description

令$F_i$是費式數列
給定$s,t$，求$\sum\limits _ {i=s}^t\binom{F_i}{2}$

Solution

這題也是有夠數學OwO
題目所求是$\sum\limits _ {i=s}^t\frac{1}{2}{F_i(F_i - 1)}$
可以想到分別求$\sum\limits _ {i=1}^nF_i$和$\sum\limits _ {i=1}^nF_i^2$

前者可以用
$$
\left[
\begin{matrix}
0 & 1 & 0 \newline
1 & 1 & 0 \newline
1 & 1 & 1
\end{matrix}
\right]
\left[
\begin{matrix}
F _ {i-2} \newline
F _ {i-1} \newline
S _ {i-1}
\end{matrix}
\right] =
\left[
\begin{matrix}
F _ {i-1} \newline
F_i \newline
S_i
\end{matrix}
\right]
$$
來得到前綴$S_i$的值

然後$F_i^2 = (F _ {i-1}+F _ {i-2})^2 = F _ {i-1}^2 + F _ {i-2}^2 + 2F _ {i-1}F _ {i-2}$
又有$F_iF _ {i-1} = (F _ {i-1}+F _ {i-2})F _ {i-1} = F _ {i-1}F _ {i-2} + F _ {i-1}^2$
所以寫成
$$
\left[
\begin{matrix}
0 & 0 & 1 & 0\newline
0 & 1 & 1 & 0\newline
1 & 2 & 1 & 0\newline
1 & 2 & 1 & 1
\end{matrix}
\right]
\left[
\begin{matrix}
F _ {i-2}^2\newline
F _ {i-1}F _ {i-2}\newline
F _ {i-1}^2\newline
Q _ {i-1}
\end{matrix}
\right] =
\left[
\begin{matrix}
F _ {i-1}^2\newline
F_iF _ {i-1}\newline
F_i^2\newline
Q_i
\end{matrix}
\right]
$$
可以得到二次的前綴

套上矩陣快速冪即可AC本題

AC 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//   __________________
//  | ________________ |
//  ||          ____  ||
//  ||   /\    |      ||
//  ||  /__\   |      ||
//  || /    \  |____  ||
//  ||________________||
//  |__________________|
//  \###################\
//   \###################\
//    \        ____       \
//     \_______\___\_______\
// An AC a day keeps the doctor away.

#pragma g++ optimize("Ofast")
#pragma loop_opt(on)
#include <bits/extc++.h>
#ifdef local
#define debug(x) (cerr<<#x<<" = "<<(x)<<'\n')
#else
#define debug(x) ((void)0)
#endif // local

using namespace std;
typedef int64_t ll;
constexpr ll N = 1025, INF = 1e18, MOD = 1000000007, K = 512, inf = 1e9;
constexpr ll modpow(ll e,ll p,ll m=MOD) {ll r=1; for(;p;p>>=1,e=e*e%m) if(p&1) r=r*e%m; return r;}

ll inv2 = modpow(2,MOD-2);
typedef vector<vector<ll>> matrix;
matrix operator*(const matrix &a, const matrix &b) {
    matrix c(a.size(), vector<ll>(b[0].size()));
    for(int i = 0; i < a.size(); i++) for(int k = 0; k < b.size(); k++) {
        ll r = a[i][k];
        for(int j = 0; j < b[k].size(); j++) c[i][j] = (c[i][j] + r*b[k][j]) % MOD;
    }
    return c;
}
matrix operator^(matrix e, ll p) {
    matrix r(e.size(), vector<ll>(e.size()));
    for(int i = 0; i < e.size(); i++) r[i][i] = 1;
    while(p) {
        if(p&1) r = r*e;
        e = e*e, p>>=1;
    }
    return r;
}
ll solve(ll n) {
    if(n == 0) return 0;
    /*
        [F _ {n-1}, F_n, S_n]
        [F _ {n-1}^2, F _ {n-1}F_n, F_n^2, Q_n]
    */
    matrix S {
        {0,1,0},
        {1,1,0},
        {1,1,1},
    };
    matrix Q {
        {0,0,1,0},
        {0,1,1,0},
        {1,2,1,0},
        {1,2,1,1},
    };
    matrix Rs = {{0},{1},{1}};
    matrix Rq = {{0},{0},{1},{1}};
    S = (S^(n-1)) * Rs;
    Q = (Q^(n-1)) * Rq;
    return (Q[3][0] - S[2][0] + MOD) * inv2 % MOD;
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    ll t,a,b;
    cin >> t;
    while(t--) {
        cin >> a >> b;
        cout << (solve(b) - solve(a-1) + MOD) % MOD << '\n';
    }
}

這題的題源好像是NPSC? 不過我還是查不太到題解，可能太水了吧QQ