题面
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;
}