问:给定一个数x,x可以为整数也可以为负数,如何对x取模,模为Mod
答:x = ((x % Mod) + Mod) % Mod
具体应用 HDU - 6185
分析:此题是递推 + 矩阵快速幂,但是因为递推式中有一个数是负数,所以需要对负数进行模运算,否则后再n = 22(不止)时出错
参考博客:https://blog.csdn.net/elbadaernu/article/details/77825979
参考代码:
#include <stdio.h>
#include <string.h>
#define N 15
#define Mod 1000000007
typedef long long ll;
const int n = 4;
struct Matrix {
ll a[N][N];
};
void print_mat(Matrix a) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
printf("%lld ", a.a[i][j]);
}
puts("");
}
}
Matrix mul(Matrix a, Matrix b) {
Matrix c; memset(c.a, 0, sizeof(c.a));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
c.a[i][j] = (((c.a[i][j] + a.a[i][k] * b.a[k][j]) % Mod) + Mod) % Mod;
}
}
}
return c;
}
Matrix qpow(Matrix a, ll b) {
Matrix res; memset(res.a, 0, sizeof(res.a));
for (int i = 0; i < n; ++i) res.a[i][i] = 1;
while (b) {
if (b & 1) res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int main() {
ll k;
while (scanf("%lld", &k) != EOF) {
ll val[N] = {0, 1, 5, 11, 36}, sum = 0;
if (k <= 4) { printf("%lld\n", val[k]); continue; }
Matrix res; memset(res.a, 0, sizeof(res.a));
res.a[0][0] = 1; res.a[0][1] = 5; res.a[0][2] = 1; res.a[0][3] = -1;
for(int i = 1; i < n; ++i) res.a[i][i - 1] = 1;
res = qpow(res, k - 4);
for (int i = 0; i < n; ++i) {
sum = (sum + res.a[0][i] * val[4 - i]) % Mod;
}
printf("%lld\n", sum);
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)