題目連結
題意:
Problem Description Function Fx,y satisfies:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiInBnauETL2ADMx0yNxczQvw1cldWYtl2LcFGdhR2Lc52YuUHZl5SdkhmLtNWYvw1LcpDc0RHaiojIsJye.jpg)
For given integers N and M,calculate Fm,1 modulo 1e9+7.
思路:
1. 遞推法
根據第二個式子可以用特征根算出來 F1,i = 1/3 * (2 ^ n - (-1) ^ n)
後面再一行行地推也就不難了
推出來
n 為奇數時,Fm.1 = 1/3 * ((2 ^ n - 1) ^ (m - 1) * 2 + 1)
n 為偶數時,Fm,1 = 1/3 * ((2 ^ n - 1) ^ (m - 1) * 2)
但是注意,/3 并不能直接除,而要乘以 3 的乘法逆元(這就是為什麼我昨天一直WA還百思不得其解)
AC代碼如下:
#include <cstdio>
typedef long long LL;
const LL mod = 1e9 + 7;
LL n, m;
LL poww(LL a, LL b) {
LL ret = 1;
while (b) {
if (b & 1) { ret *= a; ret %= mod; }
a *= a;
a %= mod;
b >>= 1;
}
return ret % mod;
}
void work() {
scanf("%I64d%I64d", &n, &m);
LL x = poww(2, n) - 1;
if (x < 0) x += mod;
LL add = poww(x, m - 1) * 2 % mod;
if (n & 1) add += 1;
add *= poww(3, mod - 2);
add %= mod;
printf("%I64d\n", add);
}
int main() {
int t;
scanf("%d", &t);
while (t--) work();
return 0;
}
2. 矩陣快速幂
參見
官方部落格
大佬的blog
AC代碼如下:
#include <cstdio>
typedef long long LL;
const LL mod = 1e9 + 7;
struct Matrix {
LL a[2][2];
Matrix(LL b = 0, LL c = 0, LL d = 0, LL e = 0) : a{b, c, d, e} {}
Matrix operator * (const Matrix& temp) 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.a[i][j] += a[i][k] * temp.a[k][j] % mod;
ret.a[i][j] %= mod;
}
}
}
return ret;
}
Matrix operator - (const Matrix& temp) const {
Matrix ret;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
ret.a[i][j] = a[i][j] - temp.a[i][j];
ret.a[i][j] %= mod;
}
}
return ret;
}
};
Matrix poww(Matrix temp, LL n) {
Matrix ret(1, 0, 0, 1);
while (n) {
if (n & 1) ret = ret * temp;
temp = temp * temp;
n >>= 1;
}
return ret;
}
void work() {
LL n, m;
scanf("%lld%lld", &n, &m);
Matrix temp = poww(Matrix(1, 2, 1, 0), n);
// printf("%lld %lld\n%lld %lld\n", temp.a[0][0], temp.a[0][1], temp.a[1][0], temp.a[1][1]);
Matrix ans(0, 0, 0, 0);
if (n & 1) ans = poww(temp - Matrix(0, 2, 1, -1), m - 1);
else ans = poww(temp - Matrix(1, 0, 0, 1), m - 1);
LL anss = ans.a[1][0] + ans.a[1][1]; anss %= mod;
printf("%lld\n", anss);
}
int main() {
int T;
scanf("%d", &T);
while (T--) work();
return 0;
}
碎碎念:
乘法逆元什麼的...
紮心了,昨天上午補第一場的12題時要求很大的數的組合數才看的
參見
組合數取模(逆元+快速幂)