题目链接 【模板】组合数 题目描述 给定两个整数  与  ()，请你计算组合数  的值，并对模数  取模。 解题思路 本题是求解组合数模一个质数的模板题。 1. 组合数公式 组合数的基本公式为：  在进行模运算时，除法不能直接计算，需要转化为乘以除数的模逆元。 公式变为：  其中  是一个质数。 2. 模逆元 因为模数  是一个质数，我们可以使用费马小定理来计算一个数  的模逆元 。 费马小定理指出：如果  是一个质数，且  不是  的倍数，则有 。 由此可得：，所以 。 计算  可以通过快速幂算法高效完成。 3. 预处理 题目包含多组测试用例，且  的最大值达到了 。如果每次查询都重新计算阶...

题目链接 矩形计数 题目描述 给定一个  的网格，每个单元格被染成白色（0）或黑色（1）。求满足以下条件的非空单元格集合  的数量：  集合中所有单元格颜色相同。 集合中任意两单元格处在同一行或同一列。  结果对  取模。 解题思路 本题的核心在于理解“任意两单元格处在同一行或同一列”这一约束。 核心条件分析 这个条件意味着一个有效的集合  中的所有单元格，必须全部位于同一行，或者全部位于同一列。任何跨越多行和多列的单元格组合（例如 L 形或  的矩形）都会存在一对不满足条件的单元格。 因此，问题转化为统计两类集合的总数：  所有单元格都在同一行且颜色相同的非空集合。 所有单元格都在同一列且颜...

题目链接 礼物清单 题目描述 旺仔哥哥收到  种不同的礼物（同种礼物彼此完全相同，数量无限）。他准备将礼物放入  个贴有不同名字的盒子中寄给朋友。 打包需满足：  同一盒子内同一种礼物不能出现两次。 每一种礼物至少放入一个盒子（可以放入多个盒子）。  求满足要求的打包方案数量，对  取模。 解题思路 这是一个组合计数问题。由于  种礼物之间的打包决策是相互独立的，我们可以先分析一种礼物有多少种合法的打包方案，然后利用乘法原理推广到所有  种礼物。 1. 单一礼物的打包方案 考虑其中任意一种礼物。我们有  个不同的盒子。  对于盒子1，我们可以选择“放”或“不放”这种礼物，有  种选择。 对于盒...

题目链接 分割序列 题目描述 给定一个长度为  的 01 字符串 ，你需要把它完全切分成若干连续子串，要求每个切分后的子串都恰好包含一个 '1'。求满足此要求的切分方案总数，结果对  取模。 解题思路 本题的核心约束是每个切分后的子串必须恰好包含一个 '1'。这为我们提供了解决问题的关键切入点。 问题分析   由于每个子串必须有且仅有一个 '1'，这意味着字符串中的每一个 '1' 都必须属于一个不同的子串。因此，切分操作必然发生在两个连续的 '1' 之间。   例如，对于字符串 ...010010...，第一个 '1' 标志着它所在子串的结束（或核心部分），而第二个 '1' 标志着下一个子串的...

题目链接 前缀平方和序列 题目描述 设一个正整数序列  的前缀和为 。若对于所有的 ， 都是完全平方数，则称该序列为一条前缀平方序列。 给定两个正整数  与 ，请你计算满足以下两个条件的前缀平方序列的数量：   序列长度为 。   对任意前缀和  均有 。   结果对  取模。 解题思路 这是一个计数问题，我们可以通过分析前缀平方序列的结构，将其转化为一个经典的组合数学问题。 1. 结构分析 根据定义，序列  的前缀和  都是完全平方数。 我们可以设 ，其中  是一个正整数。         ...      由于序列中的  都是正整数，所以对于任意 ，都有 。 这意味着 。 代入我们设定的变...

题目链接 [HNOI2008]越狱 题目描述 监狱有  个房间，每个房间关押一名犯人，共有  种宗教。如果相邻房间的犯人信仰同一种宗教，则可能发生越狱。请求出可能发生越狱的方案总数，结果对  取模。 解题思路 直接计算“至少有一对相邻犯人信仰相同”的方案数比较复杂，需要考虑多种情况并应用容斥原理。一个更简洁的思路是采用补集转化，即正难则反。 补集思想 “可能发生越狱”的对立面是“绝对不会发生越狱”。  总方案数：没有任何限制的情况下，每个犯人都有  种宗教选择，且相互独立。根据乘法原理，总的分配方案数为 。 不发生越狱的方案数：这种情况要求所有相邻房间的犯人信仰都不同。我们可以从第一个房间开始...

题目链接 墙壁划线 题目描述 一面尺寸为  的矩形墙壁由  块尺寸为  的瓷砖铺成。现从墙的左上角到右下角、右上角到左下角各画一条直线。求这两条直线与所有瓷砖边界线形成的交点总数。 解题思路 这是一个几何计数问题，可以通过坐标法和数论知识解决。 简化问题 首先，一个关键的观察是，交点的数量只与瓷砖的行列数 $a$ 和 $b$ 有关，而与每块瓷砖的具体尺寸 $x$ 和 $y$ 无关。我们可以将问题简化为在一个  的单位格网格上进行分析。 计算单条对角线的交点数 我们先考虑从左上角 (0, 0) 到右下角 (a, b) 的这条对角线。   它穿过的垂直网格线共有 $a+1$ 条（从  到 ）。  ...

题目链接 刷题统计 题目描述 牛客推出了新手入门、算法入门、算法进阶三部曲题单。 设：   — 至少刷过任意一个题单的人数  — 刷过新手入门的人数  — 刷过算法入门的人数  — 刷过算法进阶的人数  — 恰好刷过其中任意两个题单的总人数  数据保证存在唯一非负整数解，请计算同时刷过全部三部曲的人数。 解题思路 这是一个典型的集合问题，可以使用容斥原理（Principle of Inclusion-Exclusion）来解决。 我们设三个集合：  : 刷过新手入门题单的人的集合，则 。 : 刷过算法入门题单的人的集合，则 。 : 刷过算法进阶题单的人的集合，则 。  根据题意，“至少刷过任意...

题目链接 穿搭大挑战 题目描述 旺仔哥哥的衣柜里只有三类衣物：上衣、裤子和鞋子，数量分别为  件。每天出门前，他总会忘记穿一种（可能是上衣、裤子或鞋子）。 若两套穿搭在任意一件衣物的选择上不同，则视为不同的穿搭方案。请你计算，旺仔哥哥在忘穿一件衣物的前提下，一共有多少种不同的穿搭方案。 解题思路 这是一个基础的组合计数问题，可以运用加法原理和乘法原理来解决。问题要求计算在“忘穿一件衣物”的前提下的总穿搭方案数。我们可以将这个前提分解为三个互不相干的独立情况：   情况一：忘穿上衣 此时，旺仔哥哥只穿裤子和鞋子。  裤子的选择有  种。 鞋子的选择有  种。 根据乘法原理，这种情况下的穿搭方案数...

题目链接 放苹果 题目描述 我们需要将  个相同的苹果放入  个相同的盘子中，允许有的盘子空着不放。求解有多少种不同的分法。（注意：由于苹果和盘子都是相同的，所以  和  是同一种分法）。 解题思路 这是一个经典的整数划分问题。问题等价于：将整数  划分为最多  个正整数之和的方案数。我们可以使用动态规划或递归来解决。 我们定义一个函数 ，表示将  个苹果放入  个盘子的方法数。我们可以根据盘子是否为空，以及苹果和盘子的数量关系，将问题分解为更小的子问题。 可以分为以下几种情况进行讨论：   边界情况  当没有苹果时 ()，只有一种分法（所有盘子都为空），即 。 当只有一个盘子时 ()，也只有...

题目链接 好多次方 (质数模) 题目描述 给定三个正整数 ，请计算以下表达式的值：  解题思路 本题要求计算一个嵌套指数对一个固定的 质数 取模的结果。当模数  是质数时，我们可以使用 费马小定理 来简化指数，这比扩展欧拉定理更为直接。   费马小定理 该定理指出，如果  是一个质数，而整数  不是  的倍数（即 ），则有：  这个性质意味着指数是以  为周期的。对于任意正整数指数 ，我们可以将指数对  取模来降幂。   指数降幂的陷阱与修正 直接使用  作为新指数存在一个问题：当  恰好是  的倍数时，。这会导致最终计算 。  如果 ，这个结果是正确的，因为 。 但如果 ，正确结果应该是 ，...

题目链接 子数列求积 题目描述 给定一个长度为  的正整数序列 。接下来有  次独立查询，第  次查询给出一对下标  ()，请你计算区间乘积  并对模数  取模后的结果。 解题思路 本题要求我们高效地计算多次给定区间的乘积。如果对每次查询都遍历区间  进行计算，在查询次数  和区间长度都很大的情况下，总时间复杂度会达到 ，这通常会超出时间限制。 为了优化查询效率，我们可以预处理信息。类似于前缀和，我们可以使用 前缀积 的思想。   前缀积数组 我们定义一个前缀积数组 ，其中  存储序列  前  个元素的乘积模  的结果： [ P[i] = \prod_{k=1}^{i} a_k \pmod{1...

题目链接 【模板】分数取模 题目描述 给定  组数据，每组给出两个整数  和一个质数模数 。请你计算  的值。 解题思路 本题的核心是在模算术（Modular Arithmetic）的框架下执行除法运算。   模除法的转化 在常规算术中，除以一个数  等价于乘以它的倒数 。在模算术中，这个概念被模乘法逆元（Modular Multiplicative Inverse）所替代。 数  在模  意义下的乘法逆元，记作 ，是一个整数 ，满足 。 因此，原问题  就等价于计算 。   求解模乘法逆元 求解模逆元有多种方法，最常用的有扩展欧几里得算法和费马小定理。  费马小定理：该定理有一个关键的适用条...

题目链接 【模板】快速幂Ⅰ ‖ 整数 题目描述 对于给定的三个正整数 ，计算 。 解题思路 本题要求计算  的  次方对  取模的结果。这是一个经典的数论问题，通常使用快速幂（Fast Power）算法来高效解决。   朴素算法及其缺陷 最直观的方法是使用一个循环，将  连乘  次，并在每一步都对  取模。这种方法的时间复杂度是 。当  的值非常大时（例如 ），这个算法会因为超时而无法通过。   快速幂算法（二进制取幂） 快速幂算法的核心思想是利用指数  的二进制表示来减少乘法次数，将时间复杂度从  优化到 。 其原理如下： 任何一个整数  都可以表示为其二进制形式：，其中 。 因此， 可以写...