思路：在集合中任选个数组成一个新集合，求所有新集合的乘积，因为比较小，很容易想到(总数不容易求，常见的套路就是求每个数的贡献)枚举假设表示的新集合的个数，表示(是的倍数)的新集合的个数，表示因子包含的数的个数，的贡献就是。那么，且如果要计算，那么y由上面的定义可以确定的是中已经计算过了，那么可以考虑变成枚举是质数。但是对于质数，的贡献就是；对于质数，的贡献就是。而，所以需要再加上。同理对于质数，需要再加上。其它同理。于是的贡献就是。 因为，可想会很大，所以需要用到欧拉降幂，可用公式法求出，然后递推杨辉三角预处理组合数。这题貌似会卡常，加法的时候用减法代替取余，反之取余我就T了。乘法的时候，因为...

思路：按边权由小到大合并边的两个顶点，假设当前需要操作的边为，则：如果和已经在同一个组里了就不用继续合并了如果和不在同一个组里，就将和所在的组合并，则到存在一条路径上的最大值就是，且找不到比其他的路径满足该路径上的最大值小于，因为和目前只有这一条路径(边)，那么 每一阶段取出同权值的所有边，将这些边的端点用并查集两两合并，待合并完这一阶段的全部边，并查集数量为，那么当前阶段合并边的权值就是答案，否则输出。也就是说同权值的所有边要同时合并，因为未被合并的边的权值需要满足(因为题目要求和 之间不可能有任何路径满足该路径中的最大值小于或等于 。)code: #include <bits/std...

字典树需要开的空间等于节点数，而不是需要插入的数的数量，搞错经常会wa、TLE 前言：因为区间异或和不具有单调性，所以很难找到高效的算法去找到一个区间满足区间异或和不小于 且长度最短。区间问题的一个老套路是通过前缀和转化为两个点的问题，而且位运算有点难度的题都会涉及二进制，因为后面需要用到搜索，可以联想到字典树。 思路： 原数组转化为前缀和我们可以枚举区间右端点，然后找到最近的一个下标满足，那么这个合法区间就是我们可以按的二进制位去找下标：假设的第位是，的第位是，在字典树中当前遍历到的节点是，字典树下一个需要访问的值是 如果，那么，如果此时，也就是说这个二进制位可以凑出，如果沿着节点继续搜，那...

求出集合A+BA+BA+B后，把下标为质数的项的系数加起来就行。 由于某一项的系数最大可以为1e5∗1e5>9982443531e5*1e5>9982443531e5∗1e5>998244353，所以用NTTNTTNTT会出错，建议直接用FFT。 code: #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=(1<<18)+7,mod=998244353; vector<int>prime; bool vis[maxn]; in...

求出满足ai%mod≠aj%moda_i\%mod\neq a_j\%modai​%mod​=aj​%mod的最小的mod{mod}mod 之前在百度之星写过类似的题萌新，但是哪一题是求满足ai%mod=aj%moda_i\%mod= a_j\%modai​%mod=aj​%mod的最小的mod{mod}mod。 当时拿着这道题（假设ai>aja_i>a_jai​>aj​，且下面的除法都向下取整），当ai≠aja_i\neq a_jai​​=aj​时，习惯性拆成 ai−aimodmod=aj−ajmod∗moda_i-\frac{a_i}{mod}mod=a_j-\fra...

A. AquaMoon and Two Arrays 把数组A中的每个元素改为，然后不断选小于0的和大于0的进行操作，由此可以知道才有解。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+7,mod=998244353; int a[105]; vector<pair<int,int> >v; inline void solve() { int n,sum(0); v.clear(); cin>>n; for(int i=...

A. Find The Array 列出的一个：1.12.1+13.1+24.1+35.1+3+1。。。9.1+3+510.1+3+5+1 会发现，其实就是要用公差为2，首项为1的等差数列表示一个数，如果小了就补上一个数。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+7; int n; inline void solve() { int cnt(0),x(1); cin>>n; while(x<=n) { n-=x; cnt+=1; x...

第一个问题应该都是会的，主要分析第二问。定义表示对应的状态长度等于的公共子序列的数量。1.如果，则表示可以由推出。2.如果，则表示可以由推出。3.如果，则表示可以由推出。4.如果，那么，即2、3都会满足，并且都包含，所以此时需要减去一个。 还需要滚动数组。 Code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 7, mod = 1e8; int f[2][5005]; ll g[2][5005]; char A[5005],B[5005]; i...

砝码称重 dp题 Code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 7, mod = 1e9 + 7; bitset<maxn>f; int main() { int n; scanf("%d",&n); f[100000]=1; for(int i=1,x;i<=n;++i) { scanf("%d",&x); f|=(f<<x)|(f>>x...

思路：如果知道答案是某个人的子集以及这个人的编号，那么能不能算出答案，以及时间复杂度是多少，然后考虑到 生日悖论 ，因为答案是 个人的子集，所以我们任意选一个人 ，答案不是 的子集的概率是 （实际更小），那么我们只要取 30 个人，这些人的子集都不包含答案的概率就小到，几乎可以认为不可能发生。 状压求每个子集有多少人喜欢，这些子集其实是和不喜欢的货币是没关系的，所以可以离散化，存所有喜欢的货币，然后把它们离散化为。表示第个人和喜欢的货币的最大交集（状压），先存下，然后通过一种货币来状态转移，比如：。代码中状态转移的两层循环不能对调位置，一定要先枚举某一位，然后再枚举每个状态，这样才能保证后面的...

思路：这题和南京站的Evil Coordinate有着异曲同工之妙。南京的那题的解法也是一定存在某个最优情况中，相同类型的字母连续出现，然后只需要枚举种情况就可以找到最优解。南京那题我不会证，但是多画几个图后发现找不到反例，感觉也有点道理，这题看了一下证明没看懂，感觉是就是吧。 枚举出来一个状态后计算恢复它最小需要多少步可以用到前缀和，，每个前面的数量分别为，那么需要的最小的步数就是；每个前面的数量分别为，那么需要的最小的步数就是 MyCode: #include <bits/stdc++.h> using namespace std; typedef long long ll; ...

首先每个顶点的值。如果,证明如下：假设有个靠近顶点的顶点满足假设有个靠近顶点的顶点满足那么当时，将减小到会使得整棵树的美丽值增大当时，将增大到会使得整棵树的美丽值增大当时，将变成或会使得整棵树的美丽值不变或增大 定义表示时，的子树的美丽值之和，同理。 MyCode: #include <bits/stdc++.h> using namespace std; typedef long long ll; #define int long long const int maxn = 1e5 + 7, maxm = 2e5 + 7; int head[maxn],Next[maxm],to...

思路：括号匹配好题1.能碰撞的两个点坐标的奇偶性一定相同2.一般的，当所有的点不需要经过撞墙反弹后才能碰撞时，坐标奇偶性相同的点碰撞的过程就是一个括号匹配进栈出栈的过程，向右走的点进栈遇到向左走的点就出栈。3.一轮括号匹配结束后剩下的点只要左括号变右括号、右括号变左括号然后继续匹配。处理一般情况的时候多余的右括号先不动，多余的左括号变成右括号。因为撞了一次墙，所以左括号变右括号时需要挪到最左边。 MyCode: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 3...

思路：每个点被控制之后的贡献都是，所以答案可以转化为求每个点被控制的期望之和。对每个点计算合法排列（城市的排列），合法排列必须满足存在一个城市能控制点，可以用容斥/状压写，复杂度级别的。可以考虑求答案的补集，求每个点的非法排列，即所有的城市都不能控制该点，显然第个操作的城市于点的距离应该，第个操作的城市于点的距离应该，乘法计数原理即可。 MyCode: #include<bits/stdc++.h> using namespace std; const int maxn=5e4+7,mod=998244353 ; int f[maxn][25]; int qpow(int a,in...