RainAir's Blog - 数论
type: channel
link: http://blog.aor.sd.cn/tag/数论/
items: Edu 106 题解
items: contest2 题解
items: 20联赛集训day3 题解
items: CF 1107 题解
items: qbxt 10 月模拟赛 Day6
items: CF 582 题解
items: CF 1148 题解
items: CF 1418 题解
items: CF 1349 题解
items: 「CF102354」Yet Another Convolution

Edu 106 题解
type: item
date: 2021-03-19T22:15:00+08:00
description: A贪心填。先尽量填竖着的再填横着的。因为这样最多会浪费 $1$ 个，所以达到了答案的上界。求出上界判断是否 $\leq$ 即可。B枚举一个位置 $i$，前面只保留 $0$ 后面只保留 $1$，判断是否合法即可。C首先第一步横着走还是竖着走都是一样的。我们设第一步横着走。那么横着走只可能用奇数位置的 $c_i$，竖着走只可能用偶数位置的 $c_i$。枚举总共有几段，然后贪心选择最小的即可。注意要保证每个 $c_i$ 被至少选一次。D推一下式子：设 $g=\gcd(a,b)$：$$ c\frac{ab}{g}-dg = x\\ cab = gx + dg^2\\ $$设 $a' = \frac{a}{g},b' = \frac{b}{g}$：$$ ca'b' = \frac{x}{g}+d\\ a'b' = \frac{\frac{x}{g}+d}{c} $$我们枚举 $g|x$，相当于问有多少对数字 $(a',b')$，满足 $\gcd(a',b')=1$ 并且 $a'b' = x$，设 $x$ 有 $w(x)$ 个质因子，答案就是 $2^{w(x)}$。线性筛预处理 $w(x)$ 即可。复杂度 $O(n+\sqrt n)$ ，可能需要卡常。E暴力做法：枚举 $l_1,r_1$，然后以这个为开头整一个 dp：设 $f_{i,j,c}$ 表示当前考虑到位置 $s_i,t_j$ 了（这两个位置还没选），最后一次选的字符是 $c$，转移枚举下一步选哪个即可。复杂度 $O(n^4 |\Sigma|)$。复杂度瓶颈在于枚举 $l_1,r_1$，考虑把枚举这个的过程也扔到 dp 里：设 $f_{i,j,c,0/1}$ 表示考虑到位置 $s_i,t_j$，如果最后一维是 $0$，$c \in \{0,1\}$，表示当前是在枚举 $i$ 还是枚举 $j$（这里设计成先移动 $i$ 再移动 $j$ 是为了防止算枚举的方案数）；如果最后一维是 $1$ 表示当前已经选好了某个位置，$c$ 就是正常表示最后一个字母是啥了。最后枚举结束的位置把答案加起来即可。写下转移式子：对于第一种转移，有：$$ \begin{align*} f_{i,j,0,0} &\to f_{i+1,j,0,0}\\ f_{i,j,0,0} &\to f_{i,j,1,0}\\ f_{i,j,1,0} &\to f_{i,j+1,1,0}\\ f_{i,j,1,0} &\to f_{i+1,j,s[i],1}\\ f_{i,j,1,0} &\to f_{i,j+1,t[j],1} \end{align*} $$对于第二种转移，就是暴力时的转移式子，也就是：$$ \begin{align*} [c \neq s[i]]f_{i,j,c,1} &\to f_{i+1,j,s[i],1}\\ [c \neq t[j]]f_{i,j,c,1} &\to f_{i,j+1,t[j],1} \end{align*} $$不过注意到我们这样实际上只要某一个串开始选就会被计入答案了，也就是说我们会多算某一个字符串选空字符串的情况，最后减去即可。这里减去要枚举每一个区间，判断是否可行，然后减去能产生的贡献。复杂度 $O(n^2 |\Sigma|)$。空间需要稍微注意一下。F普及组树形 dp。考虑树形 dp 求直径我们会记录 $v$ 往下的最长单链的长度，这个题我们也这样搞：设 $f_{v,i}$ 表示 $v$ 子树，最长单链长度为 $i$ 的方案树，转移合并两个子树，枚举是否切割，如果不切的话， $f_{v,i} \times f_{x,j} \to f_{v,\max(i,j+1)}$，这里要求 $i+j+1 \leq k$ 即可。树形背包，两维只需要枚举到 $sz_v,sz_x$。复杂度 $O(n^2)$。转移（或许？）可以长链剖分优化，因为第二维只关于深度，转移整体平移一下，所以可以直接 $O(1)$ 继承长儿子，剩下的暴力合并打标记即可。G如果不需要修改，答案就是 $\sum_{v \in V} (\text{deg}(v) \bmod 2)$：因为我们可以构造欧拉回路，将奇点都连到一个工具点 $S$ 上，然后跑 $S$ 开始的欧拉回路，按照方向是入边还是出边来分配颜色就好了。考虑如何动态维护这个东西：一个直观的想法是根据两端点的度数奇偶性进行分类讨论，但是我们新加入的边某个端点是奇点的时候我们要依据这个端点多余的边来确定新的点的颜色，所以我们记录 $to_x$ 表示如果 $x$ 是奇点，那么 $x$ 没配对的边是哪一个；考虑现在加入边 $w=(u,v)$：如果两个端点都是偶点：那这个边给什么颜色都无所谓，不失一般性我们设这个边的颜色为 $0$；如果一个端点是奇点一个是偶点：设 $u$ 是…

contest2 题解
type: item
date: 2020-10-15T21:59:04+08:00
description: A. 寿司晚宴暴力 dp 是设 $f_{S_1,S_2}$ 表示两个人选的质因子的集合，转移直接预处理每个数的集合转移。这种题肯定是按照 $\sqrt n$ 分类讨论：对于 $\leq \sqrt n$ 的质数只有 $8$ 个，先状压，然后将其他的数字，如果最大的质因子 $> \sqrt n$ 就按照这个分类。显然每一类如果要选肯定都只会选给同一个人，所以对每一类先预处理 $g_{S}$ 表示那 $8$ 个质数的状态为 $S$ 的方案数，这里复杂度是 $O(n2^8)$ 的，然后再合并起来，复杂度是 $O(n3^8)$（可能是）。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 500+5; const int B = 8; int n,ha; inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } bool p[MAXN]; int prime[MAXN],cnt; inline void prework(){ FOR(i,2,MAXN-1){ if(!p[i]) prime[++cnt] = i; for(int j = 1;j <= cnt && i*prime[j] < MAXN;++j){ p[i*prime[j]] = 1; if(!(i%prime[j])) break; } } } int g[MAXN][(1<<B)+3],f[2][(1<<B)+3][(1<<B)+3]; int h[2][(1<<B)+3]; bool del[MAXN]; int zt[MAXN]; int main(){ prework(); scanf("%d%d",&n,&ha); FOR(i,1,B){ for(int j = prime[i];j <= n;j += prime[i]) zt[j] |= (1<<(i-1)); } FOR(i,B+1,cnt){ if(prime[i] > n) break; // printf("%d\n",prime[i]); std::vector<int> S; for(int j = prime[i];j <= n;j += prime[i]) S.pb(j),del[j] = 1; // for(auto x:S) printf("%d ",x);puts(""); int now = 0;CLR(h[now],0); h[now][0] = 1; for(auto x:S){ CLR(h[now^1],0); FOR(S,0,(1<<B)-1){ if(!h[now][S]) continue; add(h[now^1][S],h[now][S]); add(h[now^1][S|zt[x]],h[now][S]); } now ^= 1; } // DEBUG(h[now][1]); // exit(0); FOR(S,0,(1<<B)-1) g[i][S] = h[now][S]; } int now = 0;f[now][0][0] = 1; FOR(i,2,n){ if(del[i]) continue; CLR(f[now^1],0); FOR(S1,0,(1<<B)-1){ FOR(S2,0,(1<<B)-1){ if(S1&S2) continue; if(!(S2&zt[i])) add(f[now^1][S1|zt[i]][S2],f[now][S1][S2]); if(!(S1&zt[i])) add(f[now^1][S1][S2|zt[i]],f[now][S1][S2]); add(f[now^1][S1][S2],f[now][S1][S2]); } } now ^= 1; } FOR(i,…

20联赛集训day3 题解
type: item
date: 2020-10-14T17:01:00+08:00
description: 因为某些原因晚了半小时打，然后就疯狂挂题，从前二（或许？）挂到了倒一A可以考虑哈希。这里可以给每个值随机一个哈希值，合并操作定义为异或。考试的时候写的N模好像 T 飞了。。事实上这个数据一模数就能过#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl inline char nc(){ #define SIZE 1000000+3 static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE; if(p1 == p2){ p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin); if(p1 == p2) return -1; } return *p1++; #undef SIZE } template <typename T> inline void read(T &x){ x = 0;int flag = 0;char ch = nc(); while(!isdigit(ch)){ if(ch == '-') flag = 1; ch = nc(); } while(isdigit(ch)){ x = (x<<1) + (x<<3) + (ch^'0'); ch = nc(); } if(flag) x = -x; } const int MAXN = 3e5 + 5; const int H = 2; const int mod[] = {0,998244353,(int)1e9+7,(int)1e9+9,666623333,1004535809}; const int MAXM = 17; std::mt19937 g(time(NULL)); inline int qpow(int a,int n,int ha){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } struct Node{ int t[H+1]; Node(){FOR(i,1,H) t[i] = 1;} inline void gen(int id){ //FOR(i,1,H) t[i] = id;//g()%mod[i]; FOR(i,1,H) t[i] = g()%mod[i]; } inline Node operator + (const Node &x) const { Node res; FOR(i,1,H) res.t[i] = 1ll*t[i]*x.t[i]%mod[i]; return res; } inline Node inv(){ Node res; FOR(i,1,H) res.t[i] = qpow(t[i],mod[i]-2,mod[i]); return res; } inline bool operator == (const Node &x) const { FOR(i,1,H) if(x.t[i] != t[i]) return 0; return 1; } inline void debug(){ FOR(i,1,H) printf("%d ",t[i]);puts(""); } }val[MAXN],chk[MAXN],ival[MAXN]; int M; struct BIT{ #define lowbit(x) ((x)&(-(x))) Node tree[MAXN]; inline void add(int pos,Node x){ while(pos <= M){ tree[pos] = tree[pos]+x; pos += lowbit(pos); } } inline Nod…

CF 1107 题解
type: item
date: 2020-10-09T12:52:26+08:00
description: A如果长度为 $2$ 特判，否则将第一个数和剩下的数分开。B$B$ 进制下正整数的数根等价于 $\pmod {B-1}$，注意这里 $0$ 对应的答案是 $B-1$。所以答案是 $(k-1)B+x$。C双指针扫出所有相同的段，每段取前 $k$ 大即可。D观察一下发现只需要枚举 $x|n$，然后前缀和预处理+判断所有矩阵是不是全 $0/1$ 矩阵即可。时间复杂度分析一波：先考虑行的贡献，枚举的每一个 $x|n$ 都会贡献 $\frac{n}{x}$ ，那么相当于是 $\sigma_1(n)$，所以复杂度是 $O(\sigma_1(n)^2)$。这是可以分析出复杂度 $O(n^2)$ 的：考虑将 $n$ 的所有因子分类，对于 $>\sqrt{n}$ 的，只有 $O(1)$ 个，所以复杂度贡献 $O(n)$；对于 $<\sqrt{n}$ 的，因为 $\sqrt{n} \times \sqrt{n} = n$，所以他们的和顶多贡献总复杂度 $O(n)$，所以 $\sigma_1(n)$ 的量级可以认为是 $O(n)$ 的。E这种区间 dp 模型都没见过。。再看了两道CF 1132 F题目链接每次删除相同的连续段有一个性质：互不包含的删除可以任意调换相对顺序。所以我们对于一个区间可以钦定左端点是最后被删除的。这个题就可以设 $f_{l,r}$ 表示删除区间 $[l,r]$ 的代价，转移首先可以花 $1$ 代价删除 $l$，或者是枚举一个 $x$，满足 $s_l = s_x$，将 $l$ 并入 $x$，代价就是 $f_{l+1,x-1}+f_{x,r}$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 500+5; int f[MAXN][MAXN],n; char str[MAXN]; // 删除操作 一定互相包含 不交的连通块顺序无关 // 删除首先枚举 mid,那么如果str[l]==str[mid]先删除[l+1,mid-1]然后l和mid就并起来了 int main(){ scanf("%d",&n); scanf("%s",str+1); CLR(f,0x3f); FOR(i,1,n) f[i][i] = 1,f[i][i-1] = 0; FOR(len,2,n){ FOR(l,1,n-len+1){ int r = l+len-1; f[l][r] = std::min(f[l+1][r],f[l][r-1])+1; FOR(k,l+1,r){ if(str[k] == str[l]){ f[l][r] = std::min(f[l][r],f[l+1][k-1]+f[k][r]); } } } } printf("%d\n",f[1][n]); return 0; }SPOJ ZUMA题目链接这个题我们需要知道连续段的长度了，还是用左端点最后删除的思路，设 $f_{l,r,k}$ 表示区间 $[l,r]$，$l$ 前面删除导致接了 $k$ 个和 $s_l$ 相同的数的答案。转移的时候首先可以加一个数在左端点左边，$f_{l,r,k} = f_{l,r,k+1}+1$，然后如果现在可以消除了（也就是 $k-1 == K$），那就可以消除，也就是 $f_{l,r,K} = f_{l+1,r,0}$。然后就是枚举和位置 $x$ 拼在一起，$f_{l,r,k} = f_{l+1,x-1,0}+f_{x,r,\min\{k+1,K-1\}}$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #…

qbxt 10 月模拟赛 Day6
type: item
date: 2020-10-06T19:51:00+08:00
description: A假设 $a \geq b$$$ \begin{aligned} \gcd(q^a-q,q^b-1) &= \gcd(q^b-1,q^a-q^b)\\ &= \gcd(q^b-1,q^b(q^{a-b}-1))\\ &= \gcd(q^b-1,q^{a-b}-1) \end{aligned} $$使用取模加速运算即可。本质是对指数辗转相除。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl int q,a,b,ha; inline int qpow(int a,int n=ha-2){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } inline int gcd(int a,int b){ if(a < b) return gcd(b,a); if(!b) return (qpow(q,a)+ha-1)%ha; return gcd(b,a%b); } int main(){ int T;scanf("%d",&T); while(T--){ scanf("%d%d%d%d",&q,&a,&b,&ha); LL x = qpow(q,a)-1,y = qpow(q,b)-1; printf("%d\n",gcd(a,b)); } return 0; }B开 1e6 个 vector 存一下所有的倍数，每次取出最少的，如果数量变成 $0$ 了就弹掉。复杂度 $O(n \log n)$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e6 + 5; inline char nc(){ #define SIZE 1000000+3 static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE; if(p1 == p2){ p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin); if(p1 == p2) return -1; } return *p1++; #undef SIZE } template <typename T> inline void read(T &x){ x = 0;int flag = 0;char ch = nc(); while(!isdigit(ch)){ if(ch == '-') flag = 1; ch = nc(); } while(isdigit(ch)){ x = (x<<1) + (x<<3) + (ch^'0'); ch = nc(); } if(flag) x = -x; } bool p[MAXN]; int prime[MAXN],tot,d[MAXN]; inline void prework(){ FOR(i,2…

CF 582 题解
type: item
date: 2020-09-27T22:01:00+08:00
description: A手玩一下样例，我们从大到小确定每个数：将确定的数挪到序列的最前面，设确定了 $x$ 个数，那么 $x \times x$ 的方格的数都没用了，并且剩下的是一个 L 形方格。剩下的 L 形方格内对角线一定是最大值，所以我们只需要每次取最大值，将这个数和已经确定的数的 $\gcd$ 删掉即可。注意要删两次。B可以猜测一下选择方案一定是前面可能有某些增加值的地方，后面值就一直不变了。所以我们先一直跑 dp，跑到快要 T 的时候就相当于要从剩下的块中选出一些数字。由于我们可以将这个块添加到任意位置，所以选最大出现次数的数字即可。可以证明其实只需要跑 $n$ 块即可。。因为你最坏情况是每一块增加一次。这一块不增加后面完全没有必要增加。C一个经典结论是设长度为 $s$，设 $g = \gcd(s,n)$，那么新的序列的第 $i$ 位会对应原序列的 $i,i+g,i+2g,\ldots i+kg$ 位。所以我们复制一遍序列，枚举 $g|n$，将下标按照 $\bmod g$ 分类，一个点合法当前仅当它是和它一组中的最大值，一个方案合法当且仅当区间内所有点合法，倒着扫一遍维护一个指针，差分维护前缀加，求出所有长度的区间的方案数，判断 $\gcd$ 即可解决。注意这里需要预处理一下 $\gcd(i,n)$，要不然会 T。。时间还是很紧的。D设 $v_p(x)$ 表示 $x$ 的唯一分解中 $p$ 上面的指数。首先我们有 $v_p(n!) = \sum_{i \geq 1} \lfloor \frac{n}{p^i} \rfloor$，并且还有 $v_p(ab) = v_p(a)+v_p(b)$，如果考虑将 $n$ 分解成 $p$ 进制下的数，那么 $v_p(n!)$ 的每一位贡献都是将比这一位低的位都去掉的数的和。那么我们知道 $v_p(\binom n m) = v_p(n!)-v_p(m!)-v_p((n-m)!)$，我们考虑 $m+(n-m) = n$ 这个加法运算，如果在第 $i$ 位它进位了，那么在前 $i$ 位贡献不变，在第 $i+1$ 位答案会多 $1$。所以 $v_p(\binom n m)$ 就是 $n-m$ 和 $m$ 做 $p$ 进制下加法的进位次数。这个好像叫做库默尔定理？然后我们可以考虑设计一个数位dp：我们在第 $i$ 位需要知道它后面那一位是否进位才可以确定限制等因素，设 $f_{i,j,0/1,0/1}$ 从高到低考虑前 $i$ 位，进了 $j$ 次位，当前的和是否卡上界，下一位是否进位，转移细节可以看代码（我注释写的很详细了）。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3500+5; const int ha = 1e9 + 7; const int inv2 = (ha+1)>>1; int p,_,n; char str[MAXN]; int b[MAXN],a[MAXN]; int f[2][MAXN][2][2],now; // 考虑前i位 当前进位了j次 现在是否卡上界 下一位是否进位 inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } inline int calc(int n){ // sum of [x <= b,y <= n,x+y <= n] if(n < 0) return 0; if(n == 0) return 1; return (1ll*(n+1)*(n+1)%ha+ha-1ll*n*(n+1)%ha*inv2%ha)%ha; } inline int calc2(int n){ // sum of [x <= p-1,y <= p-1,x+y <= n] // p <= n+1-i => i <= n+1-…

CF 1148 题解
type: item
date: 2020-09-17T07:26:00+08:00
description: A贪心想法先把 $a$ 和 $b$ 拼成若干个 $ab$，然后如果有剩余的可以在对应的开头/结尾放，所以答案是 $c+\min(a,b)+[a \neq b]$。B枚举我们强制让这个人 $A \to B$ 选择那一班航班起飞（这样就相应 ban 掉了一些航班），然后双指针维护处对应的 $B \to C$ 最近能从哪里开始起飞，就是查一个第 $x$ 大的问题了。因为排好序了可以 $O(1)$ 直接求出。C我们只需要实现 $5$ 步内交换两个数的算法就好了：我们考虑交换 $(x,y)$ 的最一般的情况：$1 < x \leq \frac{n}{2} < y < n$，这样我们需要交换 $(x,n),(y,1),(1,n),(x,n),(y,1)$。需要额外判断一下 $x < y < \frac{n}{2}$，$\frac{n}{2} > x > y$，$x = 1,y = n$ 的各种情况，都能在五步内完成。然后直接每次将对应的值交换到正确的位置上就好了。D要看到能任意交换顺序这一点。不然就只会垃圾做法了。我们将 $a_i < b_i$ 和 $a_i > b_i$ 分成两组，发现两组内的数不能放在一起，于是可以分开处理。以解决 $a_i < b_i$ 为例：一个 sb 的想法是树状数组优化 dp，但是真的是这样么？我们考虑相邻的两个元素 $a_1 < b_1 > a_2 < b_2$，那么如果 $b$ 越小 $a$ 就越小，所以我们肯定按照 $b$ 从大到小排序，发现 $b_1 > b_2,a_2 < b_2 \Rightarrow b_1 > a_2$，这样就全满足了。另一组讨论是类似的。这个问题还是要好好读题，然后在草稿纸上画一画这些组，发现一些性质就好了。E又是可以随便排列顺序。。读题一定要仔细了。。那么我们肯定贪心从大到小排序然后考虑调整：如果一个位置想要减小，一定是找一个后面想要变大的匹配。所以我们记一下当前想要变小的位置和要变小多少，每次如果 $s_i > t_i$ 就把 $i$ 扔到集合内，否则就不断从集合头匹配即可。如果找不到前面的一个数匹配或者是最后没有匹配完就无解。感觉操作次数 $\leq 2n$ 啊不知道范围是个什么迷惑操作。。F考虑先使用归纳法证明一定有解：首先如果 bit 只有 $1$ 位一定有解：直接翻转即可。那么假设 bit 有 $k$ 位有解，接下来我们想证明 $k+1$ 位有解。发现当前翻转 $k+1$ 位上的若干位数不会影响最高位 $\leq k$ 的数，所以判断一下是否需要翻转即可。需要注意虽然我们每次决定是否翻转只是看最高位是 $k+1$ 的数，但是翻转的时候是要全部都翻转的。G好神仙啊。。。首先发现如果得到一个 $k$ 的好的集合，那么一定能得到 $\leq k$ 的好的集合。但是得到了大小为 $k$ 的不好的集合不代表你能得到 $\leq k$ 的好的集合。首先我们考虑 $O(n^2)$ 的暴力怎么做（小蒟蒻这个都不会）：如果 $k$ 是偶数：我们任意选出 $k$ 个数，每次先判断一下是不是组成一个团，如果组成直接输出，否则一定存在一对点之间没有边，删除这两个点，并且找这个点的两个相邻的点放入这个集合。如果操作 $\frac{k}{2}$ 次仍然无解，被删除的点的集合一定满足是不好的。如果 $k$ 是奇数：我们一开始找到三个点 $u,v,w$ 满足 $(u,v),(v,w)$ 边不存在，删去这三个点做子问题，可以得到一个偶数大小的不好集合，最后考虑是否要加入这三个点即可。选择三个点而不是一个点的原因是三个点可以自由决定是否加两个/三个，但是一个点加入之后你不知道是不是会破坏不好的性质。如果找不到这三个点，考虑这个图的补图，补图一定是森林，好的集合对应一个独立集，黑白染色可知一定存在 $\geq \frac{n}{2}$ 的独立集，只需要在一开始判掉有好集合的情况就好了。道理我都懂，但是正解怎么做呢？我们可以用一个复杂度 $O(2^8 n \log n)$ 的复杂度解决。首先可以将所有数的唯一分解后的形式的 $>0$ 的指数都改成 $1$，不难发现这样不影响图的形态。考虑整张图的形态显然是不行的，那么遇到这种问题一定先考虑某些特殊量是否能被算出：首先我们先考虑如何快速算一个点的度数，可以用 $f_i$ 记录包含因子 $i$ 的数的个数然后 $2^8$ 运用容斥原理算出。类似地我们选出三个点 $u,v,w$，满足 $(u,v),(v,w)$ 边不存在，并删去这三个点。我们对剩下的点，设和其他所有点都有连边的数量是 $b$，如果 $b \geq k$ 直接输出答案即可，否则剩下的 $n-3-b$ 个元素组成的集合是不好的。因为 $u,v,w$ 之间无边，所以可以全部加入到任意不好的集合内而不破…

CF 1418 题解
type: item
date: 2020-09-16T21:41:00+08:00
description: A考虑分步做合成 coal 和合成 craft 。发现我们做 $n$ 次替换后拥有的 stick 数量是 $nx-n+1$，首先要凑出 $k$ 个 coal，然后还要剩下来 $k$ 个 stick 合成，所以我们造 stick 的限制就有 $nx-n+1 \geq ky+k$，这样 $n$ 就是交易 stick 用掉的次数了，再加上 $k$（交易 coal 的次数）B把未被锁定的位置从大到小排序即可。因为无论如何放最后一个未锁定的位置的前缀和不会变，那么肯定先把所有最大的都用上去尽量 cover 掉小的贡献。Cdp。设 $f_{i,0/1}$ 表示打了前 $i$ 关，轮到玩家还是玩家的朋友打的最小代价，直接枚举转移即可。D假设两个位置选择的分别是 $x_1,x_2(x_1 < x_2)$，把坐标排好序后肯定存在一个分解点 $mid$，满足 $i \leq mid$ 都走到 $x_1$，并且 $i > mid$ 都走到 $x_2$。设第 $i$ 个坐标位置 $p_i$，发现这样的代价为 $p_n-p_1-(p_{mid+1}-p_{mid})$，所以实际上是要你支持插入，删除，维护相邻差的最大值，用两个 multiset 就可以了。E根据期望的线性性，我们只需要计算每一个 boss 对玩家的期望伤害即可。boss 可以分为两类：一类是会削玩家护盾耐久的，一类是螳臂当车的。对于会削玩家护盾耐久的，设这样的 boss 有 $m$ 个，能打到玩家的概率是 $\frac{m-a_i}{m}$（因为它在这 $m$ 个数的相对排名只有 $m$ 种情况，后面 $m-a_i$ 种是合法的）对于螳臂当车的 boss，设这样的 boss 有 $k$ 个，能打到玩家的概率是 $\frac{m+1-a_i}{m+1}$。（因为它只能选择 $m+1$ 个空插进去，后面 $m+1-a_i$ 个空是合法的）分开乘起来就行。多组询问只需要离线排序，变成了维护每次将一个削玩家耐久的变成螳臂当车的boss的操作，记录一下权值和就行了。F发现一个结论：对于任何一对 $x_1y_1 = x_2y_2(x_1 < x_2)$，都存在一对正整数 $a < b$，满足 $x_2 = \frac{x_1}{a}b,y_2 = \frac{y_1}{b}a$。[collapse status="false" title="证明"]设 $g=\gcd(x_1,x_2)$，我们构造 $a=\frac{x_1}{g},b = \frac{x_2}{g}$，不难发现 $\frac{x_1}{a}b = x_2$，接下来只需要证明 $b|y_1$即可。注意到 $b=\frac{x_2}{g} | \frac{x_2y_2}{g} = \frac{x_1y_1}{g}$，又因为有 $(b,\frac{x_1}{g}) = 1$，所以得到 $b|y_1$。[/collapse]因为 $a|x_1,b|y_1$，所以有效的 $(a,x_1)$ 只有 $O(n \log n)$ 对。现在我们去固定 $x_1$，考虑 $y_1$ 的种种限制：首先要保证 $y_1 \leq m$，其次还要保证 $\lceil \frac{L}{x_1}\rceil \leq y_1 \leq \lfloor \frac{R}{x_1} \rfloor$。我们考虑枚举一对 $(a,x_1)$，现在相当于要求快速询问是否存在一对 $(b,y_1)$ 满足如下条件：$$ \begin{aligned} y_1 \leq m\\ \lceil \frac{L}{x_1}\rceil \leq y_1 \leq \lfloor \frac{R}{x_1} \rfloor\\ \frac{x_1}{a}b \leq n\\ a < b \end{aligned} $$显然我们会贪心选择能选择的 $b$ 中最小的去判断第三个限制是否成立。第一个和第二个限制可以通过从小到大枚举 $x$ 双指针解决，第四个限制可以维护当前所有可选值的 set 解决，复杂度 $O(n \log^2 n)$。G确定性做法我们考虑枚举右端点，维护每个左端点是否合法。我们的目标是让对于每一种颜色，如果左端点区间是合法的，贡献就是 $0$，否则贡献是 $1$。那么一个左端点合法当且仅当这个位置的值是 $0$。我们每次加入一个点 $i$，设它前面第一个，第二个，第三个，第四个和它相等的是 $p_1,p_2,p_3,p_4$，我们只需要让 $(p_1,i]+1$，$(p_3,p_2]-1$，$(p_4,p_3]+1$ 即可。线段树维护最小值和最小值个数，支持区间加即可。基于这个做法我把题目小小加强了一下链接（不确定正确性详细维护方式可以见代码：#include …

CF 1349 题解
type: item
date: 2020-08-28T21:12:00+08:00
description: A因为 $\gcd$ 是指数取 min，$\text{lcm}$ 是指数取 max，所以我们对于每一个质数分开考虑。设第 $i$ 个数唯一分解后在这个质数上的指数是 $e_i$，设次小值是 $cmx$，答案贡献 $p^{cmx}$。具体实现的时候质因数分解一下即可。B首先序列里一定要有 $k$ 这个值。如果 $k$ 两边有一个 $\geq k$ 的数，就可以把这两个数都变成 $k$，然后每次选择这两个数和周围的一个数就可以合并起来了。所以等价于我们能选出一个中位数 $\geq k$ 的区间。[collapse status="false" title="证明"]我们找到一个中位数 $\geq k$ 的区间，如果这个区间没有包含所有的 $k$，那么可以任意调节长度然后对整体操作；如果包含了所有的 $k$，肯定能找到一个位置把它分成两段，某一段和为 $0$。然后直接操作即可。如果没有这样的区间，$\geq k$ 的数每次操作后不会增加，最终不会合法。[/collapse]C这个和那个真正的的生命游戏不一样！！迷惑了我半天我们发现如果一个数周围至少有一个和它相同的数，那么这两个数就会一起持续变颜色。所以我们只需要求出来所有点从什么时候开始周期变颜色就好了。可以把一开始就变色的点都扔进 queue 里，每个点向周围连边，跑一个边权为 1 的 bfs。D以下题目设 $m=\sum_{i=1}^n a_i$期望题肯定先拆开看看啊。但是我想不到怎么设。设 $E_i$ 表示到 $i$ 个点结束的答案的和（所有情况的概率乘时间的和），$E'_i$ 表示强制到 $i$ 点结束的期望时间，$P_i$ 表示在 $i$ 点结束的概率，$C$ 表示饼干从 $i$ 全部转移到 $j$ 的期望时间（显然都相等）。观察可以发现 $\sum_{i=1}^n P_i = 1,ans = \sum_{i=1}^n E_i$。首先可以得到$$ E_x = E'_x-\sum_{i=1}^n [x \neq i] (E_i+P_iC) $$就是枚举第一个到达的点是哪里，然后走过来（$E_i+P_iC$ 的理解只需要把 $E_i$ 拆成所有情况的概率乘时间的和就行了）。移项可得$$ \sum_{i=1}^n E_i = E'_x-C\sum_{i=1}^n [x \neq i]P_i $$两边对 $x$ 从 $1$ 到 $n$ 求和，可以得$$ ans = \frac{\sum_{i=1}^n E'_x-(n-1)C}{n} $$所以目标就是求 $E'_x$ 和 $C$。发现这两个东西之和目标的人有多少个饼干有关，设 $f_x$ 表示目标人有 $x$ 块饼干，到有全部饼干的期望时间。考虑这一步的饼干选出情况可以得到：$$ f_i = \begin{cases} 1+\frac{m-i}{m}(\frac{1}{n-1}f_{i+1}+\frac{n-2}{n-1}f_i)+\frac{i}{m}f_{i-1} & 0 < i < m\\ 1+\frac{n-2}{n-1}f_1+\frac{1}{n-1}f_0& i=0\\ 0&i=m \end{cases} $$这样直接高斯消元理论上就行了，但是实际上会遇到系数是模数倍数的情况然后就会被叉死。所以我们考虑能否改成一个线性递推：发现这个式子 $f$ 的系数和为 $1$，对于这样的式子我们考虑把 $f_i$ 表示成前缀和（后缀和）能消掉一个方向的所有东西就好了。为了方便我们设 $g_i = f_{i}-f_{i+1},f_{m+1}=0$，容易得到 $f_{i} = \sum_{j=i}^m g_i$。所以我们把 $0 < i < m$ 的式子拿出来看看：$$ \begin{aligned} \sum_{j=i}^m g_j = 1+\frac{n-i}{m}(\frac{1}{n-1}\sum_{j=i+1}^mg_j+\frac{n-2}{n-1}\sum_{j=i}^m g_j)+\frac{i}{m}\sum_{j=i-1}^m g_j\\ \end{aligned} $$注意到 $\frac{m-i}{m}(\frac{1}{n-1}+\frac{n-2}{n-1})+\frac{i}{m} = 1$，式子可以简化为$$ \begin{aligned} g_i = 1+\frac{n-i}{m}\times \frac{n-2}{n-1}g_i+\frac{i}{m}(g_i+g_{i+1})\\ \frac{m-i}{m(n-1)}g_i = 1+\frac{i}{m}g_{i-1}\\ g_i = \frac{m(n-1)}{m-i}+\frac{i(n-1)}{m-i}g_{i-1} \end{aligne…

「CF102354」Yet Another Convolution
type: item
date: 2020-04-25T00:48:00+08:00
description: 题目链接题目大意有两个长度为 $n$ 的序列序列 $a$ 和 $b$，要求你计算出一个长度为 $n$ 的序列满足$$c_k=\max_{\gcd(i,j)=k}|a_i-b_j|$$$n \leq 10^5$题解我们先考虑拆绝对值：最后全部取反再做一遍就好了，式子变成了$$c_k=\max_{\gcd(i,j)=k}a_i-b_j$$发现我们只需要研究 $k=1$ 的情况就好了 其余的情况可以通过拿出含有这个因子的数来转化成是 $1$ 的情况 复杂度需要乘个调和级数。我们把 $b$ 取反 题目变成了$$ c_1=\max_{\gcd(i,j)=1} a_i+b_j \\=\max_{i=1}^n (a_i+\max_{\gcd(i,j)=1}b_j) $$考虑我们枚举 $i$ 如何去计算 $\max_{\gcd(i,j)=1}b_j$：暴力枚举不太友好 我们看到 $gcd$ 就想到了$\mu$ ，但是这里是 max 不能 $mu$。于是我们考虑二分最大的$b$，设为 $b'$，你需要检验$$ \begin{align*} \max_{\gcd(i,j)=1}b_j \geq b' \\ sum_{j=1}^n [\gcd(i,j)=1][b_j \geq b'] > 0 \\ sum_{j=1}^n [b_j \geq b']\sum_{d|i,d|j}\mu(d) > 0 \\ sum_{d|i}\mu(d)\sum_{d|j}[b_j \geq b'] > 0 \end{align*} $$我们令 $sm_d = \sum_{d|j} [b_j \geq b']$。发现 $sm$ 只会根据 $b'$ 的变化而变化 于是我们想到了整体二分。整体二分的时候运用类似于莫队的移动指针的技巧 预处理因数分解和 $\mu$ 就可以快速判定了。时间复杂度 $O(nlog^3n)$ 欣慰的是这个题不卡常（最近被卡常题做晕了）#include<bits/stdc++.h> #define fi first #define se second #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; int n,A[MAXN],B[MAXN],C[MAXN]; int a[MAXN],b[MAXN],c[MAXN]; int q[MAXN],tr[MAXN]; int now,sm[MAXN]; std::vector<int> dec[MAXN]; bool p[MAXN]; int prime[MAXN],mu[MAXN],cnt; inline void prework(){ mu[1] = 1; FOR(i,2,MAXN-1){ if(!p[i]) prime[++cnt] = i,mu[i] = -1; for(int j = 1;j <= cnt && i*prime[j] < MAXN;++j){ p[i*prime[j]] = 1;mu[i*prime[j]] = -mu[i]; if(!(i%prime[j])) {mu[i*prime[j]] = 0;break;} } } FOR(i,1,MAXN-1) for(int j = i;j < MAXN;j += i) dec[j].pb(i); } inline void work(int l,int r,int L,int R){ if(l > r) return; if(L == R){ FOR(i,l,r) c[q[i]] = L; return; } int mid = (L+R)>>1; while(now > mid){ int x = tr[now--]; for(auto i:dec[x]) ++sm[i]; } while(now < mid){ int x = tr[++now]; for(auto i:dec[x]) --sm[i]; } std::vector<int> toL,toR; FOR(…