草庐IT

试题G：全排列的价值（第十三届蓝桥杯省赛Python B组）

零号记事本 2025-04-08 原文

 

【思路分析】

首先，我们先重新排列一下题目所给的例子

(3, 2, 1) : 0 + 0 + 0 = 0 ；
(3, 1, 2) : 0 + 0 + 1 = 1 ；
(2, 1, 3) : 0 + 0 + 2 = 2 ；
(2, 3, 1) : 0 + 1 + 0 = 1 ；
(1, 3, 2) : 0 + 1 + 1 = 2 ；
(1, 2, 3) : 0 + 1 + 2 = 3 ；

我们将每种排列的每个元素价值单独拿出来看看（矩阵1）

0  0  0
0  0  1
0  0  2
0  1  0
0  1  1
0  1  2

不难发现，由每种排列的每个元素价值构成的矩阵每一列的元素重复出现，进而我们把它简化一下（矩阵2），并且计算出每一列的价值和（矩阵3）

0  0  0  
   1  1  
      2  
0  1  3

这样一来规律更加清晰明了：

  1. 矩阵2为n*n，n为输入值；
  2. 矩阵2每一列在矩阵1对应列中重复的次数规律为其余列元素个数的积
    1. 例：第3列重复次数（2） = 第一列元素个数（1）* 第二列元素个数（2）
  3. 矩阵2除需要计算重复次数的列，其余列元素个数的积为n!/(计算列元素个数)
    1. 例：计算矩阵2除第 i 列元素个数积 = n! / (i+1)......(下标值从0开始)
  4. 由矩阵2每一列的价值和和出现次数得出矩阵1中每一列的价值和为重复次数与矩阵2列价值和的积
    1. 例：矩阵1第3列价值和（6） = 矩阵1第3列重复次数（2）* 矩阵2第3列价值和（3）
  5.  矩阵2每一列的元素可以构成一个首项为0，公差为1，末项为列标或行标（下标值从0开始，行标等于列表）的等差数列，则每一列的价值和可用等差数列求和公式计算
    1. 第 i 列价值和 = (0+i)*(i+1)/2

综上规律可得：

  •  n的全排列价值 = 

  • 化简一下：n的全排列价值 =

【开始敲代码】 

简单用for循环求一下阶乘验证思路

注意：python整除符号//的用法，直接做除较大数量级会引起int类型无法向float类型转换

n = int(input())
ans = 0
fac = 1
for i in range(n+1):
    if i > 0:
        fac *= i
ans = sum(range(n))*fac//2%998244353
print(ans)

 输入

3

输出

9

输入

2022

输出

593300958

因为比赛数据最大为10**6，for循环的阶乘速度远远不够，故我们采用math.factorial()加快阶乘求解，最终代码如下：

import math
n = int(input())
ans = sum(range(n))*math.factorial(n)//2%998244353
print(ans)

输入

1000000

输出

623955723

最后在压缩一下代码达成三行解题成就

import math
n = int(input())
print(sum(range(n))*math.factorial(n)//2%998244353)

解题完毕！

蓝桥试题xffcodeprepython蓝桥杯

有关试题G：全排列的价值（第十三届蓝桥杯省赛Python B组）的更多相关文章

  1. ruby - 如何进行排列以有效地定制输出 - 2

    这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][

  2. ruby - 按值降序排列散列，然后按升序键入 ruby - 2

    我有这样的哈希trial_hash={"key1"=>1000,"key2"=>34,"key3"=>500,"key4"=>500,"key5"=>500,"key6"=>500}我按值降序排列:my_hash=trial_hash.sort_by{|k,v|v}.reverse我现在是这样理解的:[["key1",1000],["key4",500],["key5",500],["key6",500],["key3",500],["key2",34]]但我希望当值相同时按键的升序排序。我该怎么做？例如:上面的散列将以这种方式排序:[["key1",1000],["key3",500

  3. Hive SQL 五大经典面试题 - 2

    目录第1题连续问题分析：解法：第2题分组问题分析：解法：第3题间隔连续问题分析：解法：第4题打折日期交叉问题分析：解法：第5题同时在线问题分析：解法：第1题连续问题如下数据为蚂蚁森林中用户领取的减少碳排放量iddtlowcarbon10012021-12-1212310022021-12-124510012021-12-134310012021-12-134510012021-12-132310022021-12-144510012021-12-1423010022021-12-154510012021-12-1523.......找出连续3天及以上减少碳排放量在100以上的用户分析：遇到这类

  4. ruby - 如何在 ruby 中组合/排列？ - 2

    我有一个熟悉的问题，看起来像是数学世界的排列/组合。如何通过ruby​​实现以下目标？badges="1-2-3"badge_cascade=[]badges.split("-").eachdo|b|badge_cascade["1","2","3"]ButIwantittobeis:=>["1","2","3","1-2","2-3","3-1","2-1","3-2","1-3","1-2-3","2-3-1","3-1-2"] 最佳答案 函数式方法:bs="1-2-3".split("-")strings=1.upto(bs.

  5. ruby - 重复排列 - 2

    我知道如何创建值数组的排列。例如:[*1..3].permutation(2)这导致以下六种排列:[1,2][1,3][2,1][2,3][3,1][3,2]但这个结果缺少三个排列，它们是相同值的组合，即:[1,1][2,2][3,3]如何获得所有排列，包括上面重复的排列？ 最佳答案 尝试#repeated_permutation:[*1..3].repeated_permutation(3).to_a>pp[*1..3].repeated_permutation(3).to_a[[1,1,1],[1,1,2],[1,1,3],[1

  6. 蓝桥杯备赛（二） - 2

    目录前言： 一、ASC分析代码实现二、 卡片分析代码实现三、 直线分析代码实现四、货物摆放分析代码实现小结：前言：  在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。 一、ASC  已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析  这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy

  7. ruby - 按组大小排列的 Active Record 顺序 - 2

    我有一个正在使用group_by的事件记录查询@foo=Foo.group_by(&:relation)然后在我正在使用的View中@foo.eachdo|group,values|groupxhasvalues.countelementsend有没有一种方法可以根据每组的数量对这些进行排序？ 最佳答案 group_by不是ActiveRecord方法，group是。group_by是一个枚举器方法。怎么样@foo=Foo.group('relation').order('count_idasc').count('id')取自"Or

  8. 蓝桥杯C/C++VIP试题每日一练之报时助手 - 2

    ?作者主页：静Yu?简介：CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家，前端知识交流社区创建者?社区地址：前端知识交流社区?博主的个人博客：静Yu的个人博客?博主的个人笔记本：前端面试题个人笔记本只记录前端领域的面试题目，项目总结，面试技巧等等。接下来会更新蓝桥杯官方系统基础练习的VIP试题，依然包括解题思路，源代码等等。问题描述：给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是：　　如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“threeo’clock”。　　如果m不为0，则将时读出来，然后将分读出来，如5

  9. arrays - ruby 中的最佳排列计数算法 - 2

    我正在尝试计算由二进制形式的1和0的P数表示的数字的数量。如果P=2，则表示的数字为0011、1100、0110、0101、1001、1010，所以计数为6。我试过:[0,0,1,1].permutation.to_a.uniq但这不是大数的最佳解决方案(P可以什么可能是最好的排列技术，或者我们是否有任何直接的数学来做到这一点？ 最佳答案 Numberofpermutationcanbecalculatedusingfactorial.a=[0,0,1,1](1..a.size).inject(:*)#=>4!=>24要计算重复项，

  10. 十四届蓝桥青少组模拟赛Python-20221108 - 2

    十四届蓝桥青少组模拟赛Python-20221108T1.二进制位数十进制整数2在十进制中是1位数，在二进制中对应10，是2位数。十进制整数22在十进制中是2位数，在二进制中对应10110，是5位数。请问十进制整数2022在二进制中是几位数？print(len(bin(2022))-2)#运行结果：11T2.晨跑小蓝每周六、周日都晨跑，每月的1、11、21、31日也晨跑。其它时间不晨跑。已知2022年1月1日是周六，请问小蓝整个2022年晨跑多少天？#样例代码1ls=[0,31,28,31,30,31,30,31,31,30,31,30,31]ans=0k=6foriinrange(1,13)

随机推荐