HDU 2254 奥运（矩阵快速幂+二分等比序列求和）

ACM

题目地址：HDU 2254 奥运

题意：
中问题不解释。

分析：
根据floyd的算法，矩阵的k次方表示这个矩阵走了k步。
所以k天后就算矩阵的k次方。
这样就变成：初始矩阵的^[t1,t2]这个区间内的v[v1][v2]的和。
所以就是二分等比序列求和上场的时候了。
跟HDU 1588 Gauss Fibonacci的算法一样。

代码：

/*
*  Author:      illuz 
  
   
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        2254.cpp
*  Create Date: 2014-08-04 10:52:29
*  Descripton:  matrix, floyd
*/

#include 
   
     #include 
    
      #include 
     
       #include 
       #include 
       
         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
        
          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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 1384 Piggy-Bank（完全背包）	下一篇：周赛 POJ 2245 Lotto

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: