HDU 6050. Funny Function (快速幂,逆元)

题面

Description

Function $F_{x,y}$ satisfies: $$ F_{1, 1} = F_{1, 2} = 1 \ F_{1, i} = F_{1, i - 1} + 2 * F_{1, i - 2} ; (i \geq 3) \ F_{i, j} = \sum_{k = j}^{j + N - 1}F_{i - 1, k} ; (i \geq 2, j \geq 1) $$ For given integers $N$and $M$,calculate $F_{m, 1}$ modulo$10^{9} + 7$.

Input

There is one integer T in the first line.

The next T lines,each line includes two integers N and M .

1<=T<=10000,1<=N,M<2^63.

Output

For each given N and M,print the answer in a single line.

Sample Input

2
2 2
3 3

Sample Output

2
33

题解

记 $F_{1, i}$为$a_{i}$ ,则 $$ a_{i} = a_{i - 1} + 2a_{i - 2} ; (i \geq 3) $$ 设 $p \neq 0, q \in \mathbb{R}$ 使得 $$ a_{i} + ka_{i - 1} = p(a_{i - 1} + ka_{i - 2}) $$ 两式对照并解得 $\left { \begin{matrix} p = -1 \ k = -2 \end{matrix} \right.$或$\left { \begin{matrix} p = 2 \ k = 1 \end{matrix} \right.$ .

  • $\left { \begin{matrix} p = -1 \ k = -2 \end{matrix} \right.$ 成立

此时记 $b_{i - 1} = a_{i} - 2a_{i - 1}$ ,易得 $$ b_{i} = (-1)^{i} $$ 故 $a_{i} - 2a_{i - 1} = (-1)^{i - 1}$ . 此时有 $$ \frac{a_{i}}{(-1)^{i}}+2\frac{a_{i - 1}}{(-1)^{i - 1}} = -1 $$ 记 $c_{i} = \dfrac{a_{i}}{(-1) ^ {i}}$ ,易得 $$ c_{i} = \frac{1}{3}(-2)^{i} - \frac{1}{3} $$ 故 $$ a_{i} = (-1)^{i}c_{i} = \frac{2^{i}}{3} + \frac{(-1)^{i - 1}}{3} $$

  • $\left { \begin{matrix} p = 2 \ k = 1 \end{matrix} \right.$ 成立

易知此时亦有 $a_{i} = \dfrac{2^{i}}{3} + \dfrac{(-1)^{i - 1}}{3}$ 成立。

综上,此时有 $$ F_{1, i} = \frac{1}{3} \cdot (-1)^{i - 1} + \frac{1}{3} \cdot 2^{i} \tag{1} $$ 此时考虑 $$ F_{2, i} = \sum_{k=i}^{i+N-1}F_{1,k}=\sum_{k=1}^{i+N-1}F_{1,k}-\sum_{k=1}^{i-1}F_{1,k} \tag{2} $$ 又,此时有
$$ \sum_{i=1}^{n}F_{1,i} = \frac{1}{3}\sum_{i=1}^{n}(-1)^{i-1}+\frac{1}{3}\sum_{i=1}^{n}2^{i} \ =\frac{1}{6}\cdot(1+(-1)^{n+1})+\frac{2}{3}\cdot(2^{n}-1) $$ 代入 $(2)$ 式可得 $$ F_{2, i} = \frac{1}{3}\cdot\frac{(-1)^{i+N}-(-1)^{i}}{2}+\frac{1}{3}\cdot(2^{N}-1)\cdot2^{i} \tag{3} $$ 类似地,易得 $$ F_{3,i}=\frac{1}{3}\cdot\frac{(-1)^{i+N}-(-1)^{i}}{2}+\frac{1}{3}\cdot(2^{N}-1)^{2}\cdot2^{i} \tag{4} $$ 此时,由归纳法易证 $$ F_{m,i}=\frac{1}{3}\cdot\frac{(-1)^{i+N}-(-1)^{i}}{2}+\frac{1}{3}\cdot(2^{N}-1)^{m-1}\cdot2^{i} \tag{5} $$ 因此 $$ F_{m,1}=\frac{1}{3}[(m;\mathbf{mod};2)+2\cdot(2^{N}-1)^{m-1}] \tag{6} $$ 用快速幂计算即可。

代码

此题 $N$和 $M$ 都是$2^{63}$ 范围,因此要用 unsigned long long

模 $k$ 乘法千万不能忘了逆元。。。这次居然很脑抽地居然把逆元忘了导致赛中自闭orz = =

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

const ull MODULO = 1e9 + 7;

ull power(ull a, ull b, ull p);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);

    int t = 0;
    cin >> t;

    while (t--) {
        ull n = 0, m = 0;
        cin >> n >> m;

        if (m == 1) {
            cout << 1 << endl;
            continue;
        }

        ull x1 = n & 1;
        ull x2 = (2 * power(power(2, n, MODULO) - 1, m - 1, MODULO)) % MODULO;

        ull ans = (x1 + x2) * 333333336 % MODULO;

        cout << ans << endl;
    }

    return 0;
}

ull power(ull a, ull b, ull p) {
    ull ans = 1 % p;

    for (; b; b >>= 1) {
        if (b & 1)
            ans = (ull)ans * a % p;
        a = (ull)a * a % p;
    }

    return ans;
}
updatedupdated2022-05-212022-05-21