如果求解： 根据莫比乌斯的一般套路，很容易想到如下转化：     即将原式转化为莫比乌斯函数后交换求和顺序。 考虑问题二的限制，有：   ，这部分就是个背包问题，假设表示前个数相加和为的方案数。 那么转移方程有： 直接转移复杂度是的，注意到等式右边可以用前缀和维护，令，则有：  显然只要先用更新，再用更新就可以把第一维去掉，复杂度。 很显然，我们只要枚举，然后跑一遍背包，总的复杂度就是，近似等于 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+7,mod=99...

求：根据容斥原理，可以分为四部分来求，每一部分都可以拆成：  考虑到可以转化，所以为了化简式子，可以：原式    式子出现莫比乌斯函数后，通常可以考虑交换求和顺序，枚举,即：   很显然，只要预处理莫比乌斯函数，然后用数论分块求解式子。 Code: #include<bits/stdc++.h> using namespace std; const int maxn=5e4+7; int mu[maxn + 1],sum[maxn+1]; int work(int n,int m) { int tot=min(n,m); int x,y,r,ans=(0); for(int i=1...

线性筛： const int maxn=5e4+7; int mu[maxn]; bool vis[maxn]; vector<int>prime; inline void init() { mu[1]=1; for(int i=2;i<maxn;++i) { if(!vis[i]) { prime.emplace_back(i); mu[i]=-1; } for(auto &j:prime) { if(i*j>=maxn) break; vis[i*j]=1; if(i%j==0) break; mu[i*j]=-mu[i]; } } }埃塞：  mu[1] ...

一.  设，则：  设表示从数的个本质不同的质因子中选个相乘，那么数的所有因子的莫比乌斯函数之和为：  如果n=1,那么本质不同的因子个数，原式；反之本质不同的因子个数，原式

思路： 一个算式肯定是加法和乘法交替的。假设乘法被分成个连续的段，加法被分成个连续的段，那么一定有。当时只想到了对每组连续的加法，如果元素不完全相同，那么运算的结果就会不同。正确的想法是：对于每组连续的加法或者乘法，如果组内的元素是相同的，那么运算的结果也是一样的。于是可以考虑将乘法分成或个连续的段、加法分成或个连续的段，那么答案就是。s2表示第二类斯特林数。 当时，会被计算两次，表示是下面的两种情况：A表示连续的加法，B表示连续的乘法 {ABAB} {BABA} code: #include<bits/stdc++.h> using namespace std; typedef ...

【传送】 KM code： #include<bits/stdc++.h> using namespace std; typedef long long ll; ll w[305][305]; // cost matrix namespace KM { ll cal(int n, int m) { vector<ll> u(n + 1), v(m + 1), p(m + 1), way(m + 1); for (int i = 1; i <= n; i++) { p[0] = i; ll j0 = 0; vector<ll> minv(m + 1, 1...

思路 线段树优化 表示线段能组成漂亮序列最多的行数。那么每次转移的时候，区间上查找与线段对应位有的所有线段，选取最大的一个线段，那么。 考虑用线段树去优化，区间上找最大的，然后得到，接着用覆盖线段的区间。因为这个只和上一个状态有关，所以可以直接覆盖。 code: #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=3e5+7; pair<int,int>t[maxn<<3],ac; bool re[maxn<<3]; #define l...

思路 方法一 状态方程： 状态方程中的表示的是数组的下标，即位置。  ，表示上一步选了，上一步选了，这一轮是选择，从上一轮开始游戏进行的回合数的期望（即从选开始计数）；  ，表示上一步选了，上一步选了，这一轮是选择，从上一轮开始游戏进行的回合数的期望（即从选开始计数） 状态转移方程：   表示事件发生的概率 运行超时的代码：code 考虑一下优化： 首先记忆化搜索保证只会对种情况进行搜索，可以考虑把每种情况里面的一层循环给消掉。 1: if(s) { int cnt=c[p2+1][a[p1]]; for(int i=p2+1;i<=n;++i) if(a[i]>a[p1]) an...

思路：考虑如何合并两个相邻的区间，假色表示从出发允许最早的时间，表示从出发允许最晚的时间，表示从到需要的时间。 比较和能否和并，其实只需要满足。有没有其它的判断方式呢，有，但是没必要：。（这不是没事找事吗，主要是补题的时候想换个思路写，想通过维护一个和一个来完成合并，画个图就知道这样比较冗余）。 所以我们需要维护区间的，同时维护一个表示到需要的时间，主要用来更新合并后的。 code: #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+7,mod=1e9+7; s...

原题链接:P4062 [Code+#1]Yazid 的新生舞会 解法一 分块  对于所有的，暴力扫描所有长度不大于的区间，即枚举左端点，然后往右扫描，长度不大于，然后维护众数出现的次数，当众数出现的次数大于区间的一半时，该区间对答案的贡献加一。这里注意不要把的维护进众数里，后面会单独计算每个的为众数的所有合法区间。 如果数组只由组成，计算以为众数的合法区间数量。表示前缀和。那么满足条件的区间需要满足：。记表示右端点取，左端点合法的数量，考虑到后移，等于加一或者减一，那么右端点取后左区间和法的数量为或 对于所有的，这些不同的数字不会超过个,枚举每种为众数的贡献，用上面的方法。 在洛谷上交18s左...

思路： 如果不考虑去重，一般都会想到可持久化字典树。 求的个数满足，很明显用字典树可以轻松的做到。求区间的内的个数的话加个可持久化，前个数组成第个版本的字典树，然后第个版本算出的值减去第个版本算出的值就是答案。 字典树求的个数满足的原理： 构建字典树时，每个节点存这个节点包含了多少个数。 搜索字典树时，假设当前访问到的第个二进制位，的这一位为。如果这一位为，字典树下一个节点的值如果是，那么得到的数一定是满足条件的，直接返回这个节点包含了多少数，然后继续访问值为的节点；如果这一位为，继续访问值为的节点。如果搜索到了字典树的叶子节点，那么直接返回这个节点包含了多少数。 考虑到一个节点内会包含多个相...

题意： 给出个数，求 ,这两个区间不同数的个数 思路： 其实只要把区间扩大一倍，就是求这个区间了 定义数组中第一次出现的数的后缀为，第次出现的数的后缀为该数第次出先时的下标。比如：原数组为，扩大一倍后为，每个数对应的后缀为。 如果某个数出现多次，而我们只算最右边的那个，我们会发现最右边的那个数的后缀一定是大于区间右端点的，其它的数的后缀一定是小于等于区间右端点的，所以我们只要把后缀大于区间右端点的数的下标取出来，然后用树状数组计算区间内有多少个数。 code; #include <bits/stdc++.h> using namespace std; typedef long lo...

思路：标程奇奇怪怪，有点绕，搞了半天才勉强看懂，还有数据水了先背包求出，表示花天学第门课最多能得多少分。设表示前门课花天学习挂科门能最多能得到的分数，那么有： 如果第门课学天，并且不及格，那么有 如果第门课学天，并且及格，那么有 其实第一维是可以滚掉的，得到，那么有：如果第门课学天，并且不及格，那么有 如果放弃第门课(一天也不学，即)，那么有。把第一维滚掉后，这里特别需要注意，虽然时符合上一个条件，如果使用上面的转移方程，得到的是，等同于，这就出问题了。 如果第门课学天，并且及格，那么有 初始，之后，即 code； #include <bits/stdc++.h> using na...

E. Permutation Shift 思路：原问题等价于把往左挪位，然后最多交换次得到原排列，求有多少种。 假设排列表示原排列，表示原排列往右挪位得到的排列，那么当时，对应位置上数字相同的个数为。 一个通常能想到的套路就是枚举，然后把排列往左挪位得到排列，然后判断排列能不能通过最多次交换得到原排列。一个很简单的结论就是，排列和排列如果有个位置不同，那么最少需要交换次，最多需要交换次。转化一下就是，排列最小需要有个对应位置的数字相同。 假设有个满足这一题的条件，满足条件的的集合，那么排列对应位置上数字相同的个数不小于,又因为当时,对应位置上数字相同的个数为。所以有不等式，而,解得。也就是说最...