首页 > 代码库 > 【bzoj3231】[Sdoi2008]递归数列 矩阵乘法+快速幂
【bzoj3231】[Sdoi2008]递归数列 矩阵乘法+快速幂
题目描述
一个由自然数组成的数列按下式定义：
对于i <= k：ai = bi
对于i > k: ai = c1ai-1 + c2ai-2 + ... + ckai-k
其中bj和 cj （1<=j<=k）是给定的自然数。写一个程序，给定自然数m <= n, 计算am + am+1 + am+2 + ... + an, 并输出它除以给定自然数p的余数的值。
输入
由四行组成。
第一行是一个自然数k。
第二行包含k个自然数b1, b2,...,bk。
第三行包含k个自然数c1, c2,...,ck。
第四行包含三个自然数m, n, p。
输出
仅包含一行：一个正整数，表示(am + am+1 + am+2 + ... + an) mod p的值。
样例输入
2
1 1
1 1
2 10 1000003
样例输出
142
题解
裸的矩乘快速幂，转移矩阵都给出来了。
将区间求和转化为前缀相减处理，对于矩阵[a1 a2 ... ak]，按照题目中的公式推出[a2 a3 ... ak+1]，然后由于求和，所以需要再开一个位置记录前缀和。
转移矩阵自己推一推就好了。
注意特判t<=k的情况。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;int n;ll p , sum[20];struct data{ ll v[20][20]; data() {memset(v , 0 , sizeof(v));} data operator*(const data a)const { data ans; int i , j , k; for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= n ; j ++ ) for(k = 1 ; k <= n ; k ++ ) ans.v[i][j] = (ans.v[i][j] + v[i][k] * a.v[k][j]) % p; return ans; } data operator^(const ll a)const { data x = *this , ans; int y = a , i; for(i = 1 ; i <= n ; i ++ ) ans.v[i][i] = 1; while(y) { if(y & 1) ans = ans * x; x = x * x , y >>= 1; } return ans; }}B , A;ll cal(ll t){ if(t < n) return sum[t]; return (B * (A ^ (t - n + 1))).v[1][n];}int main(){ int i , j; ll l , r; scanf("%d" , &n); for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &B.v[1][i]) , B.v[1][n + 1] = B.v[1][n + 1] + B.v[1][i] , sum[i] = sum[i - 1] + B.v[1][i]; for(i = n ; i >= 1 ; i -- ) scanf("%lld" , &A.v[i][n]) , A.v[i][n + 1] = A.v[i][n]; for(i = 1 ; i < n ; i ++ ) A.v[i + 1][i] = 1; n ++ , A.v[n][n] = 1; scanf("%lld%lld%lld" , &l , &r , &p); for(i = 1 ; i < n ; i ++ ) sum[i] %= p; for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= n ; j ++ ) A.v[i][j] %= p , B.v[i][j] %= p; printf("%lld\n" , (cal(r) - cal(l - 1) + p) % p); return 0;}
【bzoj3231】[Sdoi2008]递归数列 矩阵乘法+快速幂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。