首页 > 代码库 > LA3704
LA3704
https://vjudge.net/problem/UVALive-3704
参考:http://www.cnblogs.com/iwtwiioi/p/3946211.html
循环矩阵。。。
我们发现,这道题n^3logk过不了 那么就要用循环矩阵
矩阵乘法:a[i][j]=b[i][k]*c[k][j]
列向量的复杂度是O(n^2),因为只有一列,每次列向量和系数矩阵里的值对应乘起来就可以了,每次O(n),做n次。
但是系数矩阵自乘的复杂度就是O(n^3),也就意味着我们要优化系数矩阵的自乘。
我们发现,系数矩阵是一个循环矩阵。。。
也就是说系数矩阵的每一行都是上一行平移一位。
那么也就是说我们只用求第一行就可以了。
这里说明一下我们只优化了系数矩阵的自乘,没有优化快速幂中求答案的那一部分。
其实,循环矩阵的行和列是对应相等的,第一行=第一列,第二行=第二列,也就是说自乘的时候第二个元素=第一行*第二列=第一行*第二行,那么只用保存第一行就行了
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 510; struct mat { ll a[N]; } x, a, b; int n, m, d, k; mat operator * (mat A, mat B) { mat ret; memset(ret.a, 0, sizeof(ret.a)); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) if(i - j >= 0) ret.a[i] = (ret.a[i] + A.a[j] * B.a[i - j]) % m; else ret.a[i] = (ret.a[i] + A.a[j] * B.a[i - j + n]) % m; return ret; } int main() { while(scanf("%d%d%d%d", &n, &m, &d, &k) != EOF) { memset(a.a, 0, sizeof(a.a)); memset(b.a, 0, sizeof(b.a)); for(int i = 0; i < n; ++i) scanf("%lld", &x.a[i]); for(int i = 0; i <= d; ++i) a.a[i] = 1; for(int i = n - 1; i >= n - d; --i) a.a[i] = 1; b.a[0] = 1; for(; k; a = a * a, k >>= 1) if(k & 1) b = b * a; x = b * x; for(int i = 0; i < n - 1; ++i) printf("%lld ", x.a[i] % m); printf("%lld\n", x.a[n - 1] % m); } return 0; }
LA3704
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。