首页 > 其他分享 >[校内]极端题

[校内]极端题

时间:2023-08-26 10:01:29浏览次数:39  
标签:取模 排列 校内 一个 数错 极端 当且 数量

0811T1 计数练习

题意

作为一名普及组选手,小 \(A\) 喜欢数数。

一天,小 \(A\) 学习了排列相关的知识。定义一个长度为 \(n\) 的序列 \(p_{1...n}\) 是一个 \(n\) 阶排列,当且仅当 \(p_{1...n}\) 都是 \([1, n]\) 中的正整数且它们两两不同。

小 \(A\) 想数排列。为了让数排列更有趣,小 \(A\) 决定加入一个限制:

对于一个 \(n\) 阶排列 \(p\) ,小 \(A\) 会构造一个长度为 \(n\) 的序列 \(Q(p)\) ,其中 \(Q(p)_{p_i} = i\) 。小 \(A\) 称排列 \(p\) 是优秀的,当且仅当 \(p\) 的字典序严格小于 \(Q(p)\) 。即存在一个 \(i\) 使得 \(\forall 1 \le j < i, p_j = Q(p)_j\) 且 \(p_i < Q(p)_i\) 。

现在,小 \(A\) 想了一个数 \(n\),他希望对于每个 \([1, n]\) 间的 \(m\),计算好的 \(m\) 阶排列数量, 在开始数这样的排列数量前,小 \(A\) 给了你一个质数 \(mod\) ,希望你先求出好的 \(m\) 阶排列 数量对 \(mod\) 取模的结果。

为了避免极其大的输出,设 表示好的 阶排列数量对 取模的结果,你只需要 输出 ,即所有 的异或和。这样小 在自己数错的时候就有大约 的概率发现自己数错了,并重新数一遍。

Sol

由于 \(Q(Q(p)) = p\),也就是说一个排列的逆排列就是自己。

如果从 \(p\) 和 \(Q(p)\) 的视角出发,那么字典序的关系就是相反的。

那么一个排列一定会贡献 \(1\) 除非 \(p = Q(p)\)。

容易发现,如果所有轮换大小不超过 \(2\),那么组成的排列的逆排列就是自己。

我们记这样的 \(n\) 阶排列数量为 \(f_n\),那么有:

\[f_n = f_{n - 1} + (n - 1) \times f_{n - 2} \]

\[v_i = \dfrac{i! - f_i}{2} \]

标签:取模,排列,校内,一个,数错,极端,当且,数量
From: https://www.cnblogs.com/OIerBoy/p/17658397.html

相关文章

  • [校内] 计数练习
    0811T1计数练习题意作为一名普及组选手,小\(A\)喜欢数数。一天,小\(A\)学习了排列相关的知识。定义一个长度为\(n\)的序列\(p_{1...n}\)是一个\(n\)阶排列,当且仅当\(p_{1...n}\)都是\([1,n]\)中的正整数且它们两两不同。小\(A\)想数排列。为了让数排列更有趣,......
  • YTEZ校内数学集训笔记
    计数原理例题1:用一个大写的英文字母或一个阿拉伯数字给教室里的一个座位编号,总共能编出多少种不同的号码?或:\(a\wedgeb\)有\(a\)无\(b\)有\(b\)无\(a\)有\(a\)有\(b\)且:\(a\veeb\)有\(a\)有\(b\)非:\(┐a\)无\(a\)答案:英文字母共有26个,阿拉伯数......
  • 准确预测极端降水,哥伦比亚大学推出升级版神经网络 Org-NN
    内容一览:随着环境变化加剧,近年来全球极端天气现象频频出现,准确预测降水强度对人类以及自然环境都十分重要。传统模型预测降水的方差较小,偏向小雨,对极端降水预测不足。关键词:极端天气内隐学习神经网络:::hljs-center本文首发于HyperAI超神经微信公众平台~:::受台风「......
  • 极端理性主义的危险
    1、如果反对理智能力的观点能够证明理智伪造了实在,证明理智强迫我们构建了一个完全不真实的世界,那么反驳就是有效的。2、理智主义要求一个绝对封闭的体系,在那里,没有一种现今存在着的事物此前是不存在的,没有一种事物不可以依照原则从业已存在的要素中推演出来?怎么定义实在?3、人类的......
  • 7.23 校内 test
    T1题面:给一个由A,B组成的操作序列,A代表全部取反,B代表+1,每次给出操作区间l,r和一个01串,问经过操作序列中\([l,r]\)的操作后的01串,强制在线。观察性质,发现一次取反会使后面的所有+1变成-1,随便用前缀和维护即可。T2给一个网格图,每个格子有权值,切割一次的代价是被......
  • 230715校内赛
    T1串背景形貌昳丽的西克是風子国王嫡系军队的general,同时也兼任風子王国驻绿鸟国的外交官。西克喜欢在蕉含流群里与其它王国的使者蕉含流,但前段时间由于说怪话被来自绿鸟国意识形态不完全的国王驱含逐出境。西克非常愤怒,想要说出一句最怪的话,但他却忙于敢览求社的......
  • 230713校内赛
    MC党狂喜系列比赛T1命令方块题目描述实际上这道题与命令方块没有什么关系。给定\(n\)个字符串\(s_i\),将它们按给出的顺序排开。你每次可以交换任意两个字符串的位置。通过交换,这些字符串最终需要满足如下的性质:对于任意的\(i<j<k\),必须有:\(lcp(s_i,s_j)\gel......
  • 230712校内赛
    T1前缀和题目描述给你一个字符串,求所有长度为偶数的前缀在整个字符串中出现的次数和。输入格式共一行,一个字符串S输出格式共一行,输出一个整数,代表长度为偶数的前缀在整个字符串中出现的次数和样例输入数据1abababc输出数据16输入数据2isdashagayisdashagaydas......
  • 大学生毕业设计(论文)管理系统 校内互检 只能点左边高亮右边重复
    document.querySelectorAll("span.right_txt_blue").forEach(element=>{  letstr=element.getAttribute("name")  //letno=str[str.length-1]  letno=str.replace("rightblock","");  element.setAttribu......
  • 基于餐厅消费数据的隐形资助研究|校内数模竞赛分享
    前言幸亏校赛当做期末考试,才第一次这么认真点去审视一道建模同题目,前期的莽撞,对数据无奈是很崩溃的。另寻它解或是坚持耕耘都可以作为这次建模收官的关键词,因为它们真的都同时存在,并且不相上下。由于这是一道有关我们"本家"————大数据的题目,我们把数据处理当做了一个比较重要......