首页 > 代码库 > 平面 题解
平面 题解
平面
【问题描述】
二维的空间即是平面。我们在二维空间中定义直角坐标系，并用网格将空间划分为单位面积的一块一块，并给每块一个二维坐标。我们假设有一个小生命生活在二维空间中从(1,1)到(n,m)的共n×m块的矩形区域中，二维生命体一开始可以处于任意一块中，并且可以移动到上下左右相邻的一块中，但是不能越过矩形的边界。现在有一个高维的生命体闯入了这个世界，并开始制造混乱。高维生命体改变了格子的高度，使得没有任意两个相邻格子的高度相同。这样空间就变成了三维空间。但对于二维生命体来说，整个空间还是一个平面，只是它无法从一个高度较低的格子移动到相邻的高度较高的格子。二维生命体可以从任意一个格子开始移动，并在除起点外的任意一个可到达的格子处停下。一条移动的路径定义为沿途经过的所有格子的序列，路径长度为经过的格子数减1。不难发现，路径的条数是有限的。现在告诉你每一块格子的高度，你能求出所有可能路径的长度的0~k次方的和吗？由于答案可能很大，你只需要输出每个答案对12345取模后的结果。
【输入格式】
输入文件的第一行包含三个正整数n、m和k。
接下来的n行每行包含m个绝对值不超过10^9的整数，分别表示每个格子的高度。
【输出格式】
输出k+1行，每行包含一个整数。第i行的整数表示所有可能路径的长度的i−1次方之和对12345取模后的值。
【样例输入】
3 4 3
1 2 3 4
4 3 2 1
1 2 3 4
【样例输出】
38
66
136
318
DP，将格子排序，f[i]表示从i出发的路径数，g[i]为路径总长。f[i]=Σf[j]，g[i]=Σ(f[j]+g[j])，j为与i相邻的编号。
s[k][i]为从i出发的路径的k次方和，设到j的长度为aj[1...p]，s[k][j]=Σx(aj[x])^k，s[k][i]=ΣjΣx(aj[x]+1)^k。
转移：
令a=1，
复杂度：O(nm log nm +nmk2)
附代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <vector> 7 #include <queue> 8 #include <stack> 9 #include <map>10 #include <set>11 #include <string>12 #include <iomanip>13 #include <ctime>14 #include <climits>15 #include <cctype>16 #include <algorithm>17 #define clr(x) memset(x,0,sizeof(x))18 #define LL long long19 #ifdef WIN3220 #define AUTO "%I64d"21 #else22 #define AUTO "%lld"23 #endif24 25 using namespace std;26 27 const int N = 300;28 const int K = 50;29 const int mod = 12345;30 const int V[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};31 32 class point {33 public:34 int x, y, h;35 point() { }36 point(int _x, int _y, int _h) : x(_x), y(_y), h(_h) { }37 bool operator < (const point &p) const { return h < p.h; }38 } p[N*N+1];39 40 int n,m,k,a[N+1][N+1],ans[N+1],C[K+1][K+1],d[N*N+1][K+1];41 42 inline int node(int x, int y) { return (x-1)*m+y; }43 44 int main() {45 freopen("plane.in","r",stdin);46 freopen("plane.out","w",stdout);47 scanf("%d%d%d",&n,&m,&k);48 C[0][0] = 1;49 for(int i = 1; i <= k; ++i) {50 C[i][0] = C[i][i] = 1;51 for(int j = 1; j < i; ++j) {52 C[i][j] = C[i-1][j-1]+C[i-1][j];53 if(C[i][j] >= mod) C[i][j] -= mod;54 }55 }56 for(int i = 1; i <= n; ++i)57 for(int j = 1; j <= m; ++j) {58 scanf("%d", &a[i][j]);59 p[node(i, j)] = point(i, j, a[i][j]);60 }61 sort(p+1, p+n*m+1);62 for(int i = 1; i <= n * m; ++i) {63 int r = node(p[i].x, p[i].y);64 d[r][0] = 1;65 for(int v = 0; v < 4; ++v) {66 int x = p[i].x+V[v][0], y = p[i].y+V[v][1];67 int q = node(x, y);68 if(x < 1 || x > n || y < 1 || y > m || a[x][y] >= p[i].h) continue;69 d[r][0] += d[q][0];70 if(d[r][0] >= mod) d[r][0] -= mod;71 for(int j = 1; j <= k; ++j)72 for(int l = 0; l <= k; ++l) {73 d[r][j] += (C[j][l]*d[q][l])%mod;74 if(d[r][j] >= mod) d[r][j] -= mod;75 }76 }77 for(int j = 0; j <= k; ++j) {78 ans[j] += d[r][j];79 if(ans[j] >= mod) ans[j] -= mod;80 }81 }82 ans[0] -= (n * m) % mod;83 if(ans[0] < 0) ans[0] += mod;84 for(int i = 0; i <= k; ++i) printf("%d\n", ans[i]);85 return 0;86 }
平面 题解