NC229748 - Sum of gcd of Tuples (Hard) 题意 给你, ，让你求  数据范围   前置知识 莫比乌斯反演 思路 我们可以将题目给定的公式转换成下列形式：  我们可以设 接着设，可以发现表示是倍数的方案数 那么其实可以写成, 那么 接着根据莫比乌斯反演知道:  那么最终答案就是:  代码 /** * author: andif * created: 30.09.2023 16:15:06 **/ #include<bits/stdc++.h> using namespace std; #define de(x) cerr << #x &...

NC23047 - 华华给月月出题 题意 给你一个, 让你求) 数据范围  思路 通过观察发现是积性函数，那么我们可以通过欧拉筛预处理出所有的 和其他预处理不同，因为空间的问题，我们不能再开一个数组来记录，每个数字第一个质因数出现的次数 接着观察可以发现，这个函数也是完全积性函数，那么我们就可以不维护了 代码 /** * author: andif * created: 29.09.2023 19:30:41 **/ #include<bits/stdc++.h> using namespace std; #define de(x) cerr << #x <&lt...

NC229685 - 模板题【线性筛求积性函数】 题意 求正整数的所有正因数个数，次询问 数据范围   思路 不然发现一个正整数的正因数个数就是一个积性函数，那么我们可以预处理每个数字的正因数个数即可， 用上欧拉筛求积性函数来预处理 代码中表示这个数字的第一个质因数出现几次 或者也可以直接求，而不需要预处理（详情情况代码中的Solution 1） 代码 /** * author: andif * created: 29.09.2023 15:52:32 **/ #include<bits/stdc++.h> using namespace std; #define de(x) ce...

NC19922 - 局部极小值 题意 给你一个的整数矩阵，矩阵上面数字每个正好出现一次，我们认定一个格子里面的整数都小于它相邻（八相邻）格子的整数，那么称这个格子为局部极小值，现在给你一个所有局部极小值出现的位置，问你有多少种矩阵满足 数据范围   思路 定义格子的为 假设题目给的局部极小值集合为, 非局部极小值集合为, 可知 我们定义性质表示的格子为局部极小值, 那么这个题目的答案为  不难发现，这个一个矩阵的局部极小值不能超过，然后通过搜索可以发现容斥公式右边的范围最多次 OK，经过上面的讨论，我们现在的问题就是给你一些局部极小值点，然后如何求解有多少个矩阵的局部极小值点的集合包含我们给的...

NC229623 - Mike and Foam 题意 有个啤酒，第杯啤酒含有毫升的泡沫, 然后给你个架子，初始架子为空，然后让你每次取出或者放入一个啤酒，然后每次操作后要你输出当前这个架子上，互质的啤酒对数 数据范围   思路 因为是求解互质，我们其实我们可以把拆解成这种集合，其中是一个的质因数，那么考虑现在插入一个集合，那么我们要计算这个数字对于当前的贡献，其实就是计算架子上面有多少个数字和互质， 假设现在架子上面有个啤酒， 我们可以根据容斥可知，架子上和互质的数量为  我可以每次进来或者出去一个数字的时候，动态维护这么一个数量， 值得注意的是的情况需要特殊处理 代码 /** * auth...

NC19857 - 最后的晚餐 题意 给你一个圆桌，这个圆桌有个位置，现在有对情侣要入座，问你有多少种方案使得所有情侣都不相邻 数据范围  思路 我们定义性质表示第对情侣相邻， 那么这个题的答案就是 那么根据容斥原理可得:  因为每对情侣的情况是一样的，假设有对情侣相邻，那么方案数就是 那么最终的答案就是:  Notes: 个人圆排列方案数:  代码 /** * author: andif * created: 28.08.2023 23:51:46 **/ #include<bits/stdc++.h> using namespace std; #define de(x) cer...

NC16513 - 无关 题意 给你一个集合，如果一个数字不能被集合里面任意一个数字整除，那么这个数字与这个集合无关，问你区间中有多少个这种数字 数据范围  集合中都是素数 思路 首先我们可以根据前缀和的思想，把问题变成中与无关的个数减去中与无关的个数， 那么问题变成求解中与无关的整数个数， 我们设表示性质: 可以被整除 那么我们其实要求解的就是:  根据容斥原理可得  代码 /** * author: andif * created: 28.08.2023 23:14:10 **/ #include<bits/stdc++.h> using namespace std; #def...

NC15079 - 大水题 题意 给出一个数, 求到中，有多少个数不是的倍数 数据范围  思路 我们定义集合表示到的整数集合 我们定义下列的性质分别为: 表示能被整除 表示能被整除 表示能被整除 表示能被整除 表示集合中满足性质的元素 那么这个题目其实要求的就是:  根据容斥原理可得:  对于的话，因为这些数字都是质数，那么其实就等于 代码 /** * author: andif * created: 28.08.2023 22:49:12 **/ #include<bits/stdc++.h> using namespace std; #define de(x) cerr &lt...

题意 给你一个由的全排列组成的序列，问你这个序列里面有多少个的排列 思路 有两种情况 情况1 这个排列在某一个排列里面，我们把当成一个整理，那么方案数为，接着我们计算排列的方案，那么这种情况的方案数为 情况2 我们知道一个排列为 \cdots > p_n&preview=true"> 其中为最后一个满足的 那么下一个排列就为 p_n ，其中是右边大于中的最小值 情况2就是：这个排列在两个排列之间，这个时候也有两种情况 情况2.1  假设排***认的话，那么和都确定了，这个时候就剩下个未确定 那么方案数就为，但是因为个里面需要出现一个号，那么这个情况的方案数就为 情况2.2  k&am...

题意 有个圣诞树有层，每一层有个彩灯， 让你用种颜色给彩灯上色，要求圣诞树需要满足下列条件 每一层相邻两个彩灯的颜色不一样 相邻两层使用的颜色集合不一样 思路 假设我们就一层的话，我们可以用动态规划计算方案数 我们假设表示前个彩灯按顺序用了第种到第种颜色的方案数，转移方程如下 接着我们设表示前层，且第层按顺序用了第种到第种颜色的方案数，同时设表示前层的合法方案数 我们考虑 1&preview=true">(第一层比较简单), 假设没有第二个约束的话，  但是因为有了第二个约束，就变成了 那么我们就可以计算 代码 /** * author: andif * created: 31....

题意 给你一串数字，这个数字包含的数位为，然后每个数位出现的次数为，然后问你有多少个数字满足，每个都出现过，并且出现的次数都小于等于 思路 枚举每个出现的次数，然后排列组合，然后去除前导零的情况 代码 /** * author: andif * created: 27.08.2023 16:26:46 **/ #include<bits/stdc++.h> using namespace std; #define de(x) cerr << #x << " = " << x << endl #define dd(x) cerr &lt...

题意 给你一个包含个元素的数组，这个数组里面的数字都在这个区间里面，问你有多少种数组满足下面的条件 有一个，保证 a_{i + 1} > \cdots > a_{n}&preview=true"> 这个数组恰好存在一对相等的数字  思路 因为恰好存在一对相等的数字，我们设为，不然发现两个一定分别位于的两侧。 我们可以枚举这个数字（也就是最大值），然后对于除了的这个其它数字，他们都可以位于左侧，或者右侧 代码 /** * author: andif * created: 24.08.2023 23:37:00 **/ #include<bits/stdc++.h> usin...

题意 一个数字称为good数要满足两个条件  它只有和组成 它的位数之和也只有和组成  求位数的数字一共有多少个good数 思路 我们假设有个和个，那么可以知道和为，这个和最多也才 那么我们可以枚举和，然后算出，然后接着这个可以任意插在位里面，也就是 代码 /** * author: andif * created: 24.08.2023 22:45:45 **/ #include<bits/stdc++.h> using namespace std; #define de(x) cerr << #x << " = " << x <<...

题意 给你三种颜色的岛屿，数量分别为，问你在这些岛屿的任意地方建桥一共有多少种方案 建桥要满足下面的条件  同一种颜色的距离  思路 先考虑和之间建桥，可以发现中的岛屿和中的岛屿必须一一对应，不然就会违反条件， 所以我们可以枚举和直接的建桥数量，这样就知道和之间建桥的方案数，其它和的方案数是相互独立，并且求解的方案一样 代码 /** * author: andif * created: 23.08.2023 23:00:33 **/ #include<bits/stdc++.h> using namespace std; #define de(x) cerr << #x...