nyoj 302

解题思路：

首先这道题目我一开始没看懂题意，想直接寻找递推关系，但后来感觉如果这么去找递推关系会陷入死循环的。。后面参考了别人的解题报告。。先把这个题目的大意再复述一下：有一个m*n的矩阵，每个矩阵上的编号代表着国家编号，相同编号之间是有传送门，而相邻的点（上下左右）之间是可达的，问从（1,1）到（m，n）的方案数。。由于每个点之间肯定会有来回走的情况，直接找递推是非常难的。。。

别人是这么想的：把m*n的点映射到一维坐标上，再根据根据这些点是否可达建立一个邻接矩阵，最后再p次幂即可。。。

以后在这种矩阵中寻找路径方案数的问题中，如果题目中没有出现可达矩阵，那么可以先把矩阵中所有点映射到一维坐标上来，再根据点与点之间的情况建立可达矩阵，最后再做可达矩阵的幂运算。。

AC:

#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define LL long longconst int N = 105; const LL mod = 1000007; struct Matrix {int n;LL a[N][N];Matrix(){memset(a, 0, sizeof(a));} } ans, A; int node[N], n; int m, p;bool Judge(int x, int y) {if(x - n == y) return true;else if(x + n == y) return true;else if(x - 1 == y && y % n != 0) return true;else if(x + 1 == y && x % n != 0) return true;else return false; }Matrix operator * (Matrix a, Matrix b) {Matrix tmpans;tmpans.n = a.n;for(int i = 1; i <= a.n; i ++){for(int j = 1; j <= a.n; j ++){for(int k = 1; k <= a.n; k ++)tmpans.a[i][j] = (tmpans.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;}}return tmpans; }void power(int k) {while(k){if(k & 1) ans = ans * A;A = A * A;k = k >> 1;} }int main() {int T;cin >> T;while(T --){cin >> n >> m >> p;for(int i = 0; i < m; i ++) <span style="white-space:pre"> </span>{for(int j = 1; j <= n; j ++){cin >> node[i * n + j];}}for(int i = 1; i <= m * n; i ++){for(int j = 1; j <= m * n; j ++){A.a[i][j] = 0; ans.a[i][j] = 0;if(i == j) continue;if(node[i] == node[j]) A.a[i][j] = 1;else if(Judge(i, j)){A.a[i][j] = 1;}}ans.a[i][i] = 1;}ans.n = n * m; A.n = n * m;power(p);printf("%lld\n", ans.a[1][n * m] % mod);}return 0; }

总结

以上是生活随笔为你收集整理的nyoj 302的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。