【hihocoder [Offer收割]编程练习赛9 D】【简单DP】矩阵填数

2024-01-15 21:58

本文主要是介绍【hihocoder [Offer收割]编程练习赛9 D】【简单DP】矩阵填数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目4 : 矩阵填数

时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB

描述

小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的余数。

样例输入
3 2
样例输出
5

#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】矩阵填数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/610340

相关文章

基于Python实现一个简单的题库与在线考试系统

《基于Python实现一个简单的题库与在线考试系统》在当今信息化教育时代,在线学习与考试系统已成为教育技术领域的重要组成部分,本文就来介绍一下如何使用Python和PyQt5框架开发一个名为白泽题库系... 目录概述功能特点界面展示系统架构设计类结构图Excel题库填写格式模板题库题目填写格式表核心数据结构

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》:本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元

windows和Linux安装Jmeter与简单使用方式

《windows和Linux安装Jmeter与简单使用方式》:本文主要介绍windows和Linux安装Jmeter与简单使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录Windows和linux安装Jmeter与简单使用一、下载安装包二、JDK安装1.windows设

Python 异步编程 asyncio简介及基本用法

《Python异步编程asyncio简介及基本用法》asyncio是Python的一个库,用于编写并发代码,使用协程、任务和Futures来处理I/O密集型和高延迟操作,本文给大家介绍Python... 目录1、asyncio是什么IO密集型任务特征2、怎么用1、基本用法2、关键字 async1、async

Java并发编程之如何优雅关闭钩子Shutdown Hook

《Java并发编程之如何优雅关闭钩子ShutdownHook》这篇文章主要为大家详细介绍了Java如何实现优雅关闭钩子ShutdownHook,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 目录关闭钩子简介关闭钩子应用场景数据库连接实战演示使用关闭钩子的注意事项开源框架中的关闭钩子机制1.

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

使用Python开发一个简单的本地图片服务器

《使用Python开发一个简单的本地图片服务器》本文介绍了如何结合wxPython构建的图形用户界面GUI和Python内建的Web服务器功能,在本地网络中搭建一个私人的,即开即用的网页相册,文中的示... 目录项目目标核心技术栈代码深度解析完整代码工作流程主要功能与优势潜在改进与思考运行结果总结你是否曾经

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.