2013-09-23 09:01:03| 人氣2,675| 回應0 | 上一篇 | 下一篇

[UVA][矩陣] 11486 - Finding Paths in Grid

Input

The first line of input is an integer T (T<100) that indicates the number of test cases. Each case starts with a line containing only 1 integer N (1≤N≤1000000000), followed by a line having 7 integers (r₁ to r₇), which will represent the state of first row. r_i = 0 represents that, there is no player in row i, otherwise r_i will represent the player number. Player numbers will be between 1 to 4.

Output

For each case, output the number of ways to reach row N. You have to give your output modulo 1000000007.

Sample Input Output for Sample Input

3
1
1 0 2 0 3 0 4
2
1 0 2 0 3 0 4
2
1 2 3 4 0 0 0

1
0
3

Problem Setter : Md. Arifuzzaman Arif
Special Thanks : Abdullah Al Mahmud

題目描述：

一個 7 x n 的格子，一開始會有 4 個人在第一排，

每個人只能往下一排移動，移動的時候往斜上或斜下走，而且四個人不會撞在一起。

問走到最後一排的方法數有多少種。

題目解法：

先考慮將每一排的狀態壓縮，也就是 7 bit 中，有 4 個 bit 是 1。

C(7,4) = 35，因此是 35 個狀態。

這狀態可以轉移成另一個狀態，也就是走到下一排時的新狀態。

因此可以寫成一個 35x35 的矩陣 M。

而題目一開始給定第一排的狀態時，對應找到狀態編號。

寫成一個 35x1 的矩陣 A。

而答案是 M^(n-1) x A = B (35x1) 的所有元素和。

矩陣乘法使用 D&C，因此會高達 O(35^3 * log(n))。

建造 M 會比較痛苦些，使用窮舉把所有可能找出來。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#define mod 1000000007
#define DEBUG 0
using namespace std;
int R[1024], state[40];
struct mtx {
   long long v[35][35];
   mtx() {
       memset(v, 0, sizeof(v));
   }
};
mtx M;// C(7,4) = 35
void dfs(int idx, int ai, int bi, int dep) {// try all move.
   if(dep == 4) {// ai -> bi
       M.v[R[ai]][R[bi]]++;
       return;
   }
   for(; idx < 7; idx++) {
       if((ai>>idx)&1) {
           if(idx-1 >= 0 && ((bi&(1<<(idx-1)))) == 0)
               dfs(idx+1, ai, bi|(1<<(idx-1)), dep+1);
           if(idx+1 < 7 && ((bi&(1<<(idx+1)))) == 0)
               dfs(idx+1, ai, bi|(1<<(idx+1)), dep+1);
           break;
       }
   }
}
void buildMatrix() {
   int i, j, k;
   int idx = 0, cnt;
   // step1: find all column state, C(7, 4)
   for(i = 0; i < (1<<7); i++) {
       for(j = 0, cnt = 0; j < 7; j++)
           cnt += (i>>j)&1;
       if(cnt == 4)
           state[idx] = i, R[i] = idx++;
   }
   // step2: for each state, find translation matrix
   for(i = 0; i < idx; i++)
       dfs(0, state[i], 0, 0);
#if DEBUG == 1
   for(i = 0; i < 35; i++, puts(""))
       for(j = 0; j < 35; j++)
           printf("%d ", M.v[i][j]);
#endif
}
mtx multiply(mtx &x, mtx &y) {
   mtx z;
   int i, j, k;
   for(k = 0; k < 35; k++) {
       for(i = 0; i < 35; i++) {
           if(x.v[i][k] == 0)   continue;
           for(j = 0; j < 35; j++) {
               z.v[i][j] += (x.v[i][k]*y.v[k][j])%mod;
               if(z.v[i][j] >= mod)
                   z.v[i][j] %= mod;
           }
       }
   }
   return z;
}
mtx calcPow(mtx x, int y) {
   mtx ret;
   int i;
   for(i = 0; i < 35; i++)
       ret.v[i][i] = 1;
   while(y) {
       if(y&1)
           ret = multiply(ret, x);
       x = multiply(x, x);
       y /= 2;
   }
   return ret;
}
int main() {
   buildMatrix();
   int testcase;
   int n, i, j, k;
   scanf("%d", &testcase);
   while(testcase--) {
       scanf("%d", &n);
       int s = 0;
       for(i = 0; i < 7; i++) {
           scanf("%d", &j);
           if(j) s |= 1<<i;
       }
       long long A[35] = {}, B[35] = {};
       A[R[s]] = 1;
       mtx MM = calcPow(M, n-1);
       long long ret = 0;
       for(i = 0; i < 35; i++)//B[i][k] = MM.v[i][j]*A[j][k]
           for(j = 0; j < 35; j++)
               for(k = 0; k < 1; k++) {
                   B[i] += MM.v[i][j]*A[j];
                   B[i] %= mod;
               }
#if DEBUG == 1
       for(i = 0; i < 35; i++, puts("")) {
           for(j = 0; j < 35; j++)
               printf("%lld ", MM.v[i][j]);
           printf("[%lld]", A[i]);
       }
#endif
       for(i = 0; i < 35; i++)
           ret = (ret+B[i])%mod;
       printf("%lld\n", ret);
   }
   return 0;
}

我要檢舉

#11486#Finding Paths in Grid#矩陣

台長： Morris

您可能對以下文章有興趣

[UVA][dp] 10559 - Blocks

[UVA][greedy] 12321 - Gas Stations

[UVA] 12291 - Polyomino Composer

[UVA][math][JAVA] 10643 - Facing Problem With Trees

人氣(2,675) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][大整數因數分解] 11476 - Factorizing Larget Integers
此分類上一篇:[UVA][SCC&負環&DP] 11721 - Instant View of Big Bang

回應(0)