首页 > 代码库 > HDU 2254 奥运(矩阵快速幂+二分等比序列求和)
HDU 2254 奥运(矩阵快速幂+二分等比序列求和)
HDU 2254 奥运(矩阵快速幂+二分等比序列求和)
ACM
题目地址:HDU 2254 奥运
题意:
中问题不解释。
分析:
根据floyd的算法,矩阵的k次方表示这个矩阵走了k步。
所以k天后就算矩阵的k次方。
这样就变成:初始矩阵的^[t1,t2]这个区间内的v[v1][v2]的和。
所以就是二分等比序列求和上场的时候了。
跟HDU 1588 Gauss Fibonacci的算法一样。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: 2254.cpp * Create Date: 2014-08-04 10:52:29 * Descripton: matrix, floyd */ #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <algorithm> using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const int N = 20; const int SIZE = 32; // max size of the matrix const int MOD = 2008; int n, k, p1, p2; ll v1, v2, t1, t2; map<int, int> mp; struct Mat{ int n; ll v[SIZE][SIZE]; // value of matrix Mat(int _n = SIZE) { n = _n; } void init(ll _v = 0) { memset(v, 0, sizeof(v)); if (_v) repf (i, 0, n - 1) v[i][i] = _v; } void output() { repf (i, 0, n - 1) { repf (j, 0, n - 1) printf("%lld ", v[i][j]); puts(""); } puts(""); } } a, b; Mat operator * (Mat a, Mat b) { Mat c(a.n); repf (i, 0, a.n - 1) { repf (j, 0, a.n - 1) { c.v[i][j] = 0; repf (k, 0, a.n - 1) { c.v[i][j] += (a.v[i][k] * b.v[k][j]) % MOD; c.v[i][j] %= MOD; } } } return c; } Mat operator ^ (Mat a, ll k) { Mat c(a.n); c.init(1); while (k) { if (k&1) c = a * c; a = a * a; k >>= 1; } return c; } Mat operator + (Mat a, Mat b) { Mat c(a.n); repf (i, 0, a.n - 1) repf (j, 0, a.n - 1) c.v[i][j] = (b.v[i][j] + a.v[i][j]) % MOD; return c; } Mat operator + (Mat a, ll b) { Mat c = a; repf (i, 0, a.n - 1) c.v[i][i] = (a.v[i][i] + b) % MOD; return c; } Mat calc(Mat a, int n) { if (n == 1) return a; if (n&1) return (a^n) + calc(a, n - 1); else return calc(a, n/2) * ((a^(n/2)) + 1); } int main() { while (~scanf("%d", &n)) { a.init(); mp.clear(); int cnt = 0; while (n--) { scanf("%d%d", &p1, &p2); if (mp.find(p1) == mp.end()) p1 = mp[p1] = cnt++; else p1 = mp[p1]; if (mp.find(p2) == mp.end()) p2 = mp[p2] = cnt++; else p2 = mp[p2]; a.v[p1][p2]++; } a.n = cnt; scanf("%d", &k); while (k--) { scanf("%lld%lld%lld%lld", &v1, &v2, &t1, &t2); if (mp.find(v1) == mp.end() || mp.find(v2) == mp.end()) { puts("0"); continue; } v1 = mp[v1]; v2 = mp[v2]; if (t1 > t2) swap(t1, t2); if (t1 == 0) { if (t2 == 0) puts("0"); else printf("%lld\n", calc(a, t2).v[v1][v2]); } else if (t1 == 1) printf("%lld\n", calc(a, t2).v[v1][v2]); else { printf("%lld\n", ((calc(a, t2).v[v1][v2] - calc(a, t1 - 1).v[v1][v2]) + MOD) % MOD); } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。