【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 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.

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

springboot简单集成Security配置的教程

《springboot简单集成Security配置的教程》:本文主要介绍springboot简单集成Security配置的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录集成Security安全框架引入依赖编写配置类WebSecurityConfig(自定义资源权限规则

如何使用Python实现一个简单的window任务管理器

《如何使用Python实现一个简单的window任务管理器》这篇文章主要为大家详细介绍了如何使用Python实现一个简单的window任务管理器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 任务管理器效果图完整代码import tkinter as tkfrom tkinter i

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

使用EasyExcel实现简单的Excel表格解析操作

《使用EasyExcel实现简单的Excel表格解析操作》:本文主要介绍如何使用EasyExcel完成简单的表格解析操作,同时实现了大量数据情况下数据的分次批量入库,并记录每条数据入库的状态,感兴... 目录前言固定模板及表数据格式的解析实现Excel模板内容对应的实体类实现AnalysisEventLis

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链