本文主要是介绍【hihocoder [Offer收割]编程练习赛9 D】【简单DP】矩阵填数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目4 : 矩阵填数
时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB
-
3 2
样例输出 -
5
描述
小Hi在玩一个游戏，他需要把1, 2, 3, ... NM填入一个N行M列的矩阵中，使得矩阵每一行从左到右、每一列从上到下都是递增的。
例如如下是3x3的一种填法：
136 247 589
给定N和M，小Hi希望知道一共有多少种不同的填法。
输入
一行包含两个整数N和M。
对于60%的数据 1 <= N <= 2, 1 <= M <= 100000
对于20%的数据 N = 3, 1 <= M <= 100
对于100%的数据 1 <= N <= 3, 1 <= M <= 100000
输出
输出一共有多少种不同的填法。由于结果可能很大，你只需输出答案模109+7的余数。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
LL qpow(LL x, int p)
{LL y = 1;while (p){if (p & 1) y = y * x % Z;x = x * x % Z;p >>= 1;}return y;
}
int main()
{while(~scanf("%d%d", &n, &m)){LL ans = 1;for (int i = 2; i <= n * m; ++i)ans = ans * i % Z;for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){ans = ans * qpow(i + j - 1, Z - 2) % Z;}}printf("%lld\n", ans);}return 0;
}
/*
【题意】
n * m个点放入矩阵使得行列有序【分析】
★这种思维模式很重要★
其实，我们发现，这题，不光最后形成的n * m的矩阵需要满足横增竖增的条件，其他的任何一个子矩阵也都要满足这个条件。
也就是说。我们在形成一个n * m矩阵的过程中，从细到巨，每一步也都要符合目标的限制条件。
这样做法就有了——
我们for循环形成i*j的矩阵，之前的
(i - 1) * (j - 1)、(i)*(j - 1)、(i - 1)*j 这三种类型的矩阵显然都是满足目标条件的。
那么其实我们只要调整使得(i, j)这个点也满足这个条件即可。
如何调整呢？
与(i, j)产生关系的是其上面的i - 1个点和其左边的j - 1个点
这一共i + j - 1个点中，我们要调整(i, j)为相对最大的，所以/=(i + j - 1)
这样全部扫描一遍。就AC啦！*/这篇关于【hihocoder [Offer收割]编程练习赛9 D】【简单DP】矩阵填数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
