BZOJ 3231: [Sdoi2008]递归数列( 矩阵快速幂 )

矩阵乘法裸题..差分一下然后用矩阵乘法+快速幂就可以了.

---------------------------------------------------------------------------------

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 20;

typedef long long ll;

typedef int mat[maxn][maxn];

ll n, m;

int p, k, ans, sm;

int b[maxn], c[maxn];

mat Q, res, tmp;

inline void upd(int &x, int t) {

if((x += t) >= p) x -= p;

if(x < 0) x += p;

}

void Init() {

ans = sm = 0;

scanf("%d", &k);

for(int i = 0; i < k; i++)

scanf("%d", b + i);

for(int i = 0; i < k; i++)

scanf("%d", c + i);

scanf("%lld%lld%d", &m, &n, &p);

for(int i = 0; i < k; i++)

upd(sm, b[i]);

}

void makeMatrix() {

Q[0][0] = 1;

Q[1][0] = 0;

for(int i = 1; i <= k; i++)

Q[0][i] = Q[1][i] = c[i - 1];

for(int i = 2; i <= k; i++)

for(int j = 0; j <= k; j++)

Q[i][j] = (j + 1 == i);

for(int i = 0; i <= k; i++)

for(int j = 0; j <= k; j++)

res[i][j] = (i == j);

}

void Mult(mat &a, mat b) {

for(int i = 0; i <= k; i++)

for(int j = 0; j <= k; j++)

tmp[i][j] = 0;

for(int i = 0; i <= k; i++)

for(int v = 0; v <= k; v++)

for(int j = 0; j <= k; j++)

upd(tmp[i][j], ll(a[i][v]) * b[v][j] % p);

for(int i = 0; i <= k; i++)

for(int j = 0; j <= k; j++)

a[i][j] = tmp[i][j];

}

int calc(ll x) {

makeMatrix();

x -= k;

for(; x; x >>= 1, Mult(Q, Q))

if(x & 1) Mult(res, Q);

int ret = 0;

upd(ret, ll(res[0][0]) * sm % p);

for(int i = 1; i <= k; i++)

upd(ret, ll(res[0][i]) * b[k - i] % p);

return ret;

}

void Work() {

if(--m <= k) {

for(int i = 0; i < m; i++)

upd(ans, -c[i]);

} else

upd(ans, -calc(m));

upd(ans, calc(n));

printf("%d\n", ans);

}

int main() {

Init();

Work();

return 0;

}

---------------------------------------------------------------------------------

3231: [Sdoi2008]递归数列

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 526  Solved: 229
[Submit][Status][Discuss]

Description

HINT

对于100%的测试数据：

1<= k<=15

1 <= m <= n <= 1018

Source