Leetcode 3426. Manhattan Distances of All Arrangements of Pieces

ops/2025/1/21 16:02:47/
  • Leetcode 3426. Manhattan Distances of All Arrangements of Pieces
    • 1. 解题思路
    • 2. 代码实现
  • 题目链接:3426. Manhattan Distances of All Arrangements of Pieces

1. 解题思路

这道题很惭愧,一开始没有搞定,后来看了答案想了想,发现就是一个单纯的数学题,而且是不太难的那种,唉,就很惭愧。

首先,考察每一个pair会被选到的次数,这个事实上就是 C n m − 2 k − 2 C_{nm-2}^{k-2} Cnm2k2,即事先将目标的两个位置占上,剩下的 k − 2 k-2 k2个点能在图上摆放的所有情况就是其可以被选中的次数。且任意两个点组成的pair这个重复次数都是完全相同的。

然后,我们只需要考虑这个 n × m n\times m n×m的矩阵当中所有位置对的曼哈顿距离之和即可。

然后,考虑到曼哈顿距离的定义,事实上我们又可以将横向和纵向分开考虑,我们只考虑任意两个点的横向距离差,显然这个值就是:

d = m 2 × ∑ i = 0 n − 2 ∑ j = i + 1 n − 1 ( j − i ) = m 2 × ∑ i = 0 n − 2 ( n − i ) ( n − i − 1 ) 2 d = m^2 \times \sum\limits_{i=0}^{n-2}\sum\limits_{j=i+1}^{n-1} (j-i) = m^2 \times \sum\limits_{i=0}^{n-2}\frac{(n-i)(n-i-1)}{2} d=m2×i=0n2j=i+1n1(ji)=m2×i=0n22(ni)(ni1)

同理,纵向距离差之和即为:

d = n 2 × ∑ i = 0 m − 2 ( m − i ) ( m − i − 1 ) 2 d = n^2 \times \sum\limits_{i=0}^{m-2}\frac{(m-i)(m-i-1)}{2} d=n2×i=0m22(mi)(mi1)

因此,总的答案就是:

D = C n m − 2 k − 2 ⋅ ( m 2 × ∑ i = 0 n − 2 ( n − i ) ( n − i − 1 ) 2 + n 2 × ∑ i = 0 m − 2 ( m − i ) ( m − i − 1 ) 2 ) D = C_{nm-2}^{k-2} \cdot (m^2 \times \sum\limits_{i=0}^{n-2}\frac{(n-i)(n-i-1)}{2} + n^2 \times \sum\limits_{i=0}^{m-2}\frac{(m-i)(m-i-1)}{2}) D=Cnm2k2(m2×i=0n22(ni)(ni1)+n2×i=0m22(mi)(mi1))

2. 代码实现

给出python代码实现如下:

MOD = 10**9+7Factorials = [1 for _ in range(10**5+1)]
Revs = [1 for _ in range(10**5+1)]
for i in range(2, 10**5+1):Factorials[i] = (i * Factorials[i-1]) % MODRevs[i] = pow(Factorials[i], -1, mod=MOD)def C(n, m):return (Factorials[n] * Revs[n-m] * Revs[m]) % MOD if n >= m else 0class Solution:def distanceSum(self, m: int, n: int, k: int) -> int:vertical = 0for i in range(n-1):vertical += (n-i) * (n-1-i) // 2vertical = (vertical * m * m) % MODhorizon = 0for i in range(m-1):horizon += (m-i) * (m-1-i) // 2horizon = (horizon * n * n) % MODreturn C(n*m-2, k-2) * (vertical + horizon) % MOD

提交代码评测得到:耗时67ms,占用内存25.5MB。


http://www.ppmy.cn/ops/151942.html

相关文章

2025年01月17日Github流行趋势

项目名称:MiniCPM-o 项目地址url:https://github.com/OpenBMB/MiniCPM-o 项目语言:Python 历史star数:14181 今日star数:371 项目维护者:yiranyyu, iceflame89, yaoyuanTHU, LDLINGLINGLING, tc-mb 项目简介…

Java测试开发平台搭建(九)前端

1. 搭建前端vue环境 Vue3 安装 | 菜鸟教程 2. 创建项目 1.进入ui vue ui 2. create项目 3. 成功之后添加插件: cli-plugin-router vue-cli-plugin-vuetify 4. 添加依赖 axios 5. 点击任务开始运行 如果报错: 修改vue.config.jsconst { defineConfig }…

如何使用 Python 进行文件读写操作?

大家好,我是 V 哥。今天的内容来介绍 Python 中进行文件读写操作的方法,这在学习 Python 时是必不可少的技术点,希望可以帮助到正在学习 python的小伙伴。 以下是 Python 中进行文件读写操作的基本方法: 一、文件读取&#xff1…

mongoose 支持https踩坑纪实

简述 mongoose是C编写的嵌入式web服务,它能够支持https协议,可以简单的部署,但要做到完美部署,不是那么容易。 部署方法 本人使用的是最新的7.16版,以前版本似乎是要通过修改 头文件中的 MG_ENABLE_SSL 宏定义&…

电梯系统的UML文档05

Dispatcher 不控制实际的电梯组件,但它在软件系统中是重要的。每一个电梯有一个ispatcher,主要功能是计算电梯的移动方向、移动目的地以及保持门的打开时间。它和系统中除灯控制器以外的几乎所有控制对象交互。 安全装置也是一个环境对象,它…

如何使用 Redis 作为高效缓存

如何使用 Redis 作为高效缓存 Redis(Remote Dictionary Server)是一个高性能的 内存存储系统,通常被用作 缓存 来加速数据访问,提高应用的吞吐量和响应速度。本文详细讲解如何使用 Redis 作为高效缓存,包括基本原理、…

DNVS许可管理

在全球经济一体化的大背景下,合规管理成为了企业持续稳健发展的关键要素。DNVS许可管理作为一种国际领先的许可认证体系,以其严格的标准和专业的审核流程,帮助企业实现合规管理,为企业的稳健发展保驾护航。 一、DNVS许可管理的核…

【学习笔记15】如何在非root服务器中,安装属于自己的redis

一、下载安装包 官网下载黑马程序员给的安装包(redis-6.2.6) 二、将安装包上传至服务器 我将安装包上传在我的文件夹/home/XXX,指定路径中/src/local/redis/,绝对路径为/home/XXX/src/local/redis/解压安装包 XXXomega:~$ cd …