当前位置：首页 > news >正文

解决leetcode第3539题.魔法序列的数组乘积之和

news 2025/5/20 7:03:53

3539.魔法序列的数组乘积之和

难度：困难

问题描述：

给你两个整数M和K，和一个整数数组nums。

一个整数序列seq如果满足以下条件，被称为魔法序列：

seq的序列长度为M。

0<=seq[i]<nums.length

$2^{seq[0]}$ + $2^{seq[1]}$ +...+ $2^{seq[M-1]}$ 的二进制形式有K个置位。

这个序列的数组乘积定义为prod(seq)=(nums[seq[0]]*nums[seq[1]]*...*nums[seq[M-1]])。

返回所有有效魔法序列的数组乘积的总和。

由于答案可能很大，返回结果对 $10^{9}$ +7取模。

置位是指一个数字的二进制表示中值为1的位。

示例1:

输入:M=5,K=5,nums=[1,10,100,10000,1000000]

输出:991600007

解释:

所有[0,1,2,3,4]的排列都是魔法序列，每个序列的数组乘积是 $10^{13}$ 。

示例2:

输入:M=2,K=2,nums=[5,4,3,2,1]

输出:170

解释:

魔法序列有[0,1]，[0,2]，[0,3]，[0,4]，[1,0]，[1,2]，[1,3]，[1,4]，[2,0]，[2,1]，[2,3]，[2,4]，[3,0]，[3,1]，[3,2]，[3,4]，[4,0]，[4,1]，[4,2]和[4,3]。

示例3:

输入:M=1,K=1,nums=[28]

输出:28

解释:

唯一的魔法序列是[0]。

提示:

1<=K<=M<=30

1<=nums.length<=50

1<=nums[i]<=108

问题分析：

Leetcode中的有些题很难读懂，有时甚至读不懂，本题就是这样，但读懂之后，要做出来，也很不容易。

读懂并理清数据关系：对于一个给定的nums整数数组，其数组长度为n，与之对应有另一个长度也是n的数组a，a中的元素是0到n-1的n个值，本问题的关键是从a中选取m个元素组成全排列，并找出这些全排列中的魔法数组，然后再根据找出的魔法数组序列，依次求出魔法数组乘积并求和，再对 $10^{9}$ +7取模。

从a中的n个元素中选取m个元素组成全排列，我的方法是：

先找出a中n个元素的全排列，然后再取出这个全排列中每个元素的前m个元素组成一个没有重复新的排列，这就是要求的结果。函数get_n_m_all_array(n,m)在函数insert_one_to_array(one,a)、函数get_n_all_array(a)的配合下完成这个功能。

函数is_magic_list(a,k)，其功能是检验一个数组a是不是有k个置位，如果有，返回True，否则返回False

函数get_all_migic_array(n,m,k)，其功能是从列表[0,1,2,......,n-1]取出m个元素的全排列中找出所有的魔法数组并返回

主程序则根据魔法数组序列计算魔法数组乘积并求和，最后输出结果对 $10^{9}$ +7取模的值。

程序如下：

#将one整数插入到a列表中的各个位置，生成全排列并返回
def insert_one_to_array(one,a):b=[]n=len(a)for i in range(n+1):left=a[:i]right=a[i:]k=left+[one]+rightb.append(k)return b#生成列表a中元素的全排列并返回
def get_n_all_array(a):n=len(a)if n==1:return [a]elif n==2:return [a,a[::-1]]else:left=a[0]right=a[1:]c=get_n_all_array(right)b=[]for i in c:c=insert_one_to_array(left,i)b.extend(c)return b#生成从列表[0,1,2,......,n-1]n个元素中取出m个的全排列并返回
def get_n_m_all_array(n,m):a=list(range(n))alist=get_n_all_array(a)b=[]for i in alist:c=i[:m]if c in b:continueelse:b.append(c)return b#检验一个数组a是不是有k个置位，如果有，返回True，否则返回False
def is_magic_list(a,k):s=0for i in a:s=s+2**is=bin(s)c=s.count('1')return True if c==k else False
#从列表[0,1,2,......,n-1]n个元素中取出m个的全排列里面找出所有的魔法数组序列并返回
def get_all_migic_array(n,m,k):a=get_n_m_all_array(n,m)b=[]for i in a:if is_magic_list(i,k):b.append(i)return b#主程序
nums=eval(input('pls input nums='))
m=int(input('pls input m='))
k=int(input('pls input k='))
n=len(nums)#找出所有的魔法数组序列
a=get_all_migic_array(n,m,k)#通过循环对所有的魔法数组求魔法数组乘积并求和
s=0
for i in a:b=1for j in i:b=b*nums[j]s=s+b#输出结果对109+7取模的结果
print(s%(10**9+7))

运行实例一

pls input nums=[3,5,7,4]

pls input m=3

pls input k=3

2334

运行实例二

pls input nums=[5,4,3,2,1]

pls input m=3

pls input k=3

1350

运行实例三

pls input nums=[3,2,1]