RainAir's Blog - 计数
type: channel
link: http://blog.aor.sd.cn/tag/计数
items: 小c的岛屿 题解
items: Topcoder UniqueMST
items: ARC119F AtCoder Express 3
items: ARC 115 题解
items: CF1450 题解
items: AGC038 部分题解
items: 20zr联赛集训day17
items: 20zr联赛集训day15
items: 20联赛集训day13 题解
items: contest5 题解

小c的岛屿 题解
type: item
date: 2021-07-09T08:04:08+08:00
description: 简单题还能写挂，感觉没救了啊 /fd /fd /fd题解由于保证每个点至少有一个出边，所以操作次数等于走的边数+1。由于这个步数可能到达 $\infty$，对于这种问题算期望的一种方法是：对于所有还没有停止的情况，算它们的概率的和。所以考虑一个暴力的 dp：设 $f_{i,j,k}$ 表示当前走了 $i$ 步（注意这里的步是指尝试加入了几次边，而不是走过的边数，最后答案减一即可），已经加入了 $j$ 条边，现在在点 $k$ 的概率。如果能预处理出 $h_i$ 表示 $n$ 个点 $i$ 条边的非连通图在所有 $i$ 条边的图中的概率，就可以用 $\sum_{i,j,k} f_{i,j,k} \times h_j$ 来统计答案了。但是这里 $i$ 没有限制，所以状态就是 $O(\infty)$ 的（先考虑如何转移：根据定义可以得到：$$ \begin{align} f_{0,0,1} &= 1\\ f_{i,j,k} &= \sum_{(v,k) \in E} (f_{i-1,j,v}\times (1-p_v) + f_{i-1,j-1,v} \times p_v) \times \frac{1}{out_v} \end{align} $$考虑尝试去掉第一维。设 $g_{i,j} = \sum_{x} f_{x,i,j}$，考虑如何对 $g_{i,j}$ 转移，显然有：$$ g_{i,j} = \sum_{(v,j) \in E} (g_{i,v} \times (1-p_v) + g_{i-1,v} \times p_v) \times \frac{1}{out_v} + [i = 0 \and j = 1] $$后面那个加号是为了修正 $f_{0,0,1}$ 的情况。直接高斯消元可以达到 $O(n^9)$ 的复杂度。一种经典优化是我们按照 $i$ 分类进行优化，我们处理到 $i$ 的时候一定已经知道了 $g_{i-1,*}$ 的值，所以每一次消元只有 $O(n)$ 个变量，直接做复杂度是 $O(n^5)$ 的。高斯消元实际上是求解 $Ax = b$，不难发现每次变化的只有 $b$，所以我们预处理 $A^{-1}$，每次就可以 $O(n^2)$ 直接求出 $x = A^{-1}b$ 了，复杂度 $O(n^4)$。现在考虑如何计算那个 $h$。这其实就是前几天的模拟。设 $f_{i,j}$ 表示 $i$ 个点 $j$ 条边的无向连通图个数，显然 $h_i = \binom{\binom n 2}{i} - f_{n,i}$。暴力转移：$$ f_{i,j} = \binom{\binom n 2}{i} - \sum_{k=1}^{i-1} \binom{i-1}{k-1} \sum_{x=0}^{j} f_{k,x} \binom{\binom{i-k}{2}}{j-x} $$考虑写成 Poly 的形式：设 $F_i$ 是 $f_{i,j}$ 的生成函数，转移可以写成：$$ F_i = (1+x)^{\binom n 2} - \sum_{k=1}^{i-1} \binom{i-1}{k-1} F_k \times (1+x)^{\binom {i-k}{2}} $$将 $F$ 看成关于 $(1+x)$ 的函数，需要转移 $O(n)$ 次，每次要进行 $n$ 次多项式平移，复杂度 $O(n^4)$。最后手动展开 $(1+x)^i$ 就好了。写一下我怎么写挂的：入度出度写反了，转移的时候拿的 $out_k$ 而不是 $out_v$，输了两次，双输！代码#include <bits/stdc++.h> #define fi first #define se second #define DB double #define U unsigned #define P std::pair #define LL long long #define LD long double #define pb emplace_back #define MP std::make_pair #define SZ(x) ((int)x.size()) #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 = 100 + 5; const int M…

Topcoder UniqueMST
type: item
date: 2021-06-05T16:46:45+08:00
description: 题意问有多少个 $n$ 个点的完全图，满足所有边权在 $[1,K]$ 内，并且最小生成树只有一个。答案对质数 $p$ 取模。$n \leq 50,K \leq 10^9,\max(n,K)+1 \leq p \leq 10^9$。题解先考虑如何求最小生成树：将所有边从小到大排序，按照顺序选择两个端点不在一个联通块的边，并合并这两个联通块。所以我们可以考虑按照权值去考虑这些边：设 $f_{n,k}$ 表示考虑有 $n$ 个点的完全图，唯一的最小生成树的边权都 $\leq k$ 的方案数。考虑如何转移：假设树上有边权为 $k$ 的边，我们删去这些在最小生成树上边权为 $k$ 的边，发现这个树一定分成了若干个联通块。联通块之间的边边权一定要 $>k$ 否则方案不唯一；然后就分解成了若干个子问题。发现这个方案数和权值都和每个联通块的大小有关，所以我们考虑去做计数。先考虑一个暴力是枚举联通块的大小。为了防止计算重复，我们按顺序枚举：先枚举 $1$ 号点所在的联通块大小 $s_1$，再枚举剩下的点中最小权值的点所在的联通块大小 $s_2,s_3,\ldots,s_m$，这样可以得到选点方案数就是 $\binom{n-1}{s_1-1}\binom{n-s_1-1}{s_2-1}\ldots$。接下来我们要计算生成树个数，这个题相当于就是每有一条连向大小为 $x$ 的块的边，对答案贡献就要乘上一个 $x$，根据经典的结论可以得到这样的方案数是 $(\sum s_i)^{m-2} \prod s_i = n^{m-2} \prod s_i$。然后需要决定剩下的边的权值，每个都可以填 $(k,K]$ 中的任何一个数字，方案数是 $(K-k)^{\binom n 2 - \sum_{i=1}^m \binom {s_i}{2} - (m-1)}$。把这些东西乘起来就是这一个枚举对答案的贡献。但是直接暴力显然不可行，我们考虑如何优化转移。这种优化显然是写成每次加入一个大小为 $x$ 的块，乘上的系数是和 $x$ 有强相关的式子的形式，所以可以写成：$$ n^{-2}(K-k)^{\binom n 2 +1}\sum_{s_1,s_2,\ldots,s_m} \prod_{i=1}^m \binom{n-\sum_{j=1}^{i-1} s_j - 1}{s_i-1} s_i n (K-k)^{-(\binom {s_i} 2 + 1)} f_{s_i,k-1} $$发现系数只需要知道之前的 $\sum s_i$ 就好了。这样每次转移可以再跑一个 dp：设 $g_i$ 表示已经 $\sum s_i = i$ 的系数和，转移枚举当前的联通块长度，乘上对应的权值即可。也就是$$ g_i = \sum_{j=1}^i g_{i-j} \binom{n-(i-j)-1}{j-1} j n (K-k)^{-(\binom j 2 +1)} f_{j,k-1} $$然后最后乘上外面那一堆东西就好了。复杂度 $O(n^3K)$。这题 $K$ 很大，所以我们会去思考是否可以插值。打表发现 $f_n$ 关于 $k$ 是一个 $O(n^2)$ 项多项式，所以 $O(n^5)$ 求出点值然后写个插值就过了。需要稍微卡下常数，因为 tc 的机子并不快。。。证明：设 $f_i$ 的次数是 $d_i$，根据最初的暴力式子可以得到：$$ \begin{aligned} d_n &= \binom n 2 + 1 + \sum_i (d_{s_i}-\binom {s_i} 2 -1)\\ &= O(n^2) - \sum_i d_{s_i}-O(s_i^2) \end{aligned} $$所以取 $d_i = O(i^2)$ 大概就能放过去。代码（代码内附赠一组我一开始跑的很慢的数据）#include <bits/stdc++.h> #define fi first #define se second #define DB double #define U unsigned #define P std::pair #define LL long long #define LD long double #define pb emplace_back #define MP std::make_pair #define SZ(x) ((int)x.size()) #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) #…

ARC119F AtCoder Express 3
type: item
date: 2021-05-17T15:51:00+08:00
description: 题意有一条长度为 $n+1$ 的村庄，编号依次为 $0\ldots n$。最初，在 $i$ 和 $i+1$ 之间有双向通行的铁路。现在有两个铁路公司（A 和 B）要争夺这些村庄。$0$ 和 $n$ 这两个村庄同时被两个铁路公司占有，$[1,n-1]$ 内的村庄会被其中一个铁路公司占有。假设某个铁路公司占有的村庄按顺序排序为 $a_1,a_2,\ldots,a_m$，那么在 $(a_1,a_2),(a_2,a_3),\ldots,(a_{m-1},a_m)$ 之间也会有一条双向铁路。现在已经确定了某些村庄的分配情况，需要求出有多少种分配剩下的村庄的方案，使得从 $0$ 到 $n$ 的最短路 $\leq k$ 。每条铁路经过的时间都为 $1$。对 $10^9+7$ 取模。$n \leq 4000$题解神仙题。。。启发：很多转移带环的最短路问题，如果最后有要求按照某个顺序 dp 的话，可以考虑这个环会影响哪些情况，有时候可以「假设」满足这些情况，然后发现在假设不成立的时候这个限制是更松的，就可以对了。还是按照套路，先考虑如何判定某个状态是否合法：我们就从 $0$ 开始按照边跑一个 bfs，判断一下 $n$ 位置的最短路是否 $\leq k$ 就好了。所以如果想计数的话，应该是把这个最短路过程压入 dp 状态。直接暴力记录所有点的 $dis_v$ 数组显然不可以，所以我们考虑一下这个图的最短路有没有什么特别之处。这个题由于是无向边，最短路需要考虑如何处理往回走的情况。发现往回走到达某个点是最短路，当且仅当它在一大块和它一样的字母中，这样先跳到后面的那个字母，再倒着走回来。也就是说，倒着走是这种情况：这样会比正着走可能要快一点。其实就是相当于花费了 $2$ 的代价，可以倒着遍历。也就是说，我们每次扩展一个新的字符，如果这个字符的最短路最后一步是从右边过来的，那么一定是从它右边的第一个和它不一样的位置过来的（中间可能经过多个一样的位置）。还是以 $i$ 位置的 A 举例，首先如果倒着走，一定是有一次从 $i$ 的前面跑到 $i$ 的后面了，而 A 显然不可能跨过中间的 A 直接到后面的 A，所以只有可能是从 $i$ 前面的 B 跳到了后面，然后后面这个 B 到 $i$ 这一段一定全是 A（因为恰好是下一个 B），所以只能一步步倒回去。所以也不会多次跨过 A（因为无论如何都在 A 后面第一个 B 停下）。联想到在结束的时候最后一个位置一定同时是 A 和 B，所以我们在考虑一段的时候可以假设这一段后面就是和它不一样的一个字母（也就是支持倒着走）。设 $f_{i,j,k,0/1}$ 表示考虑了前 $i$ 个位置，当前位置的最短路是 $j$，和当前位置不同的字母最靠后的位置的最短路是 $k$，当前位置的字母是 A/B，假设下一个字母和当前位置的字母不同的方案数。转移我们以要填 A 为例。如果 $i+1$ 位置是 A，$i$ 位置是 B：那么还是维持之前的假设的，所以 $j,k$ 这两个最短路可以直接拿过来用，转移就考虑从 B 走过来（$k+1$）还是从上一个 A 走过来（$j+1$）就好了。如果 $i+1$ 位置是 A，$i$ 位置也是 A：这时候就破坏了之前的假设，考虑是否能 fix。如果想从上一个 B 转移过来，看起来是不影响的，因为我们接下来要假设 $i+1$ 后面一个位置是不同的，所以用 $k+2$ 更新；如果想从上一个 A 转移过来，要讨论一下：如果上一个 $A$ 的最短路没有通过假设的 $B$ 走过来的，说明这个最短路还是对的，用 $j+1$ 更新；如果上一个 $A$ 的最短路是倒着从假想的 $B$ 走过来的，如果我们用 $j+1$ 更新，肯定会比 $k+2$ 大（因为这实际上是用 $k+3$ 更新：上一次这个 $j$ 是用 $k+2$ 更新，这次又要 $+1$），所以这个问题不用担心对于填 B 是类似的。复杂度 $O(n^3)$。优化的话，考虑在这个假设下，$|j-k| \leq 2$（因为可以花最多 $2$ 步相互到达），所以就可以优化到 $O(n^2)$ 了。代码#include <bits/stdc++.h> #define fi first #define se second #define DB double #define U unsigned #define P std::pair #define LL long long #define LD long double #define pb emplace_back #define MP std::make_pair #define SZ(x) ((int)x.size()) #define all(x) x.begin(),x.end() #define CLR(i,…

ARC 115 题解
type: item
date: 2021-03-23T21:37:00+08:00
description: A先将其压成二进制数，考虑两个人 $(i,j)$ 他们不可能拥有相同的通过数当且仅当它们不同的位的数量是奇数，也就是 $x\text{ xor } y$ 有奇数个 $1$。然后我赛时直接冲了个 FWT 过了稍微分析一下，发现两个数不同，当且仅当一个是 $1$ 一个是 $0$，我们只考虑这些不同的位置，发现恰好一个 $1$ 的数量是奇数一个是偶数。反过来也是对的。所以统计一下有奇数个 $1$ 和偶数个 $1$ 的数量，乘起来就好了。B$C_{i,j} = A_i + B_j$。我们考虑第 $i$ 行，就是 $B$ 序列整体加上了一个 $A_i$，于是差分一下就可以算出 $B$ 序列的差分序列。考虑列也可以算出 $A$ 序列的差分序列。首先如果通过不同的行/列算出的差分序列不同一定是无解的。现在关键在于决定 $A_1,B_1$ 是啥，知道这个之后就可以推出来了。首先我们有 $A_1+B_1 = C_{1,1}$，然后由于这个题要求非负整数，根据差分数组的前缀和的最小值，我们还有两个限制 $A_1 \geq l_1,B_1 \geq l_2$。随便找出一组可行解那么它一定满足限制。C我们考虑估一个答案的下界：$\lfloor \log_2 n \rfloor$。因为所有形如 $2^x$ 的数字组成了一个团。那么我们考虑如何构造能让如果 $x|y$，那么 $a_x \neq a_y$：可以想到如果 $x$ 整除 $y$，那么 $x$ 唯一分解后 $\sum e_i$ 一定是小于 $y$ 的，所以我们构造这个序列即可。注意特判 $1$，所以其实整体都是要加一的，那个下界也应该是 $\lfloor \log_2 n \rfloor + 1$。另一种做法：考虑将 $n$ 的因数分解为若干组，每一组满足两两都是除数/被除数的关系。每一组都是一个团，所以我们只需要找到这些团的最大值然后加一就好了。简化一下：也就是找到所有因数的答案的最大值加一就好了。D欧拉回路有一个经典的结论：求出一个 dfs 树后等价于 dfs 树上若干个树环（只包含一个非树边）的异或。但是这个题需要求有 $k$ 个奇点的数量怎么办？我们求欧拉回路的时候如果有奇点一般的处理方法都是建立一个新点，连所有奇点。由于奇点一定有偶数个，所以连完之后一定变成一个欧拉图。我们考虑用类似的方法计数：首先肯定要分联通块考虑，设一个 $n$ 个点 $m$ 条边的联通块，选出恰好 $k$ 个奇度点（$k$ 是偶数）的方案是：首先我们要选出这 $k$ 个点向新点连边，这一部分方案是 $\binom{n}{k}$；然后我们要选一些新图上的树环，但是注意：由于我们钦定了奇度点，所以我们必须选择连接之后新产生的环，而原先的环的数量显然是 $m-n+1$。所以答案就是 $\binom n k 2^{m-n+1}$。多个联通块卷起来就好了。复杂度 $O(n^2)$。可以用分治+NTT之类技巧优化到 $O(n \log^2 n)$ 但是没必要。E考虑容斥。我们枚举把它划分成 $t$ 个段，每段内都要相同，那么每段内可以取的数字就是从 $1$ 到这一段的最小值，对答案的贡献是 $(-1)^{n-t}$。我们可以把 $(-1)^{n-t}$ 看成 $(-1)^n \times (-1)^t$，然后 dp：设 $f_i$ 表示当前划分了前 $i$ 个数，并且 $i$ 是最后一段的结尾的答案。转移枚举这一段的开头是啥：$$ f_i = -\sum_{j=1}^i f_{j-1} \times \min(a_{j},a_{j+1},\ldots,a_{i}) $$这样直接做是 $O(n^2)$ 的。考虑优化：这个 min 让我们想到用单调栈维护。我们维护一个递增的单调栈 $b_1,b_2,\ldots,b_m$，这里的 $b_i$ 表示在原序列的位置。不难发现在 $[b_i,b_{i+1})$ 的 $j$，都满足 $\min(a_j,a_{j+1},\ldots,a_i)$ 是 $a_{b_i}$。所以我们对于栈内的位置 $i$，维护一下 $sm_i = \sum_{k=b_i}^{b_{i+1}-1} f_{k-1}$，再维护一个整体的和 $now = \sum_{i=1}^m b_ism_i$ 即可。弹栈的时候相当于合并区间，更新一下即可。复杂度 $O(n)$。F比较神仙。。。考虑一个最显然的暴力：将第 $i$ 个点当前在哪里看成一个 $k$ 元组，每个这样的 $k$ 元组看成一个新图点，权值是所有点的和；新图中的两个点有连边当且仅当它们可以一步到达。问从 $S$ 到 $T$ 的最小瓶颈路。看到最大值最小我们会去思考二分：设二分了一个上界 $L$，我们现在只需要保留所有权值 $\leq L$ 的状态，检查 $S,T…

CF1450 题解
type: item
date: 2020-12-07T21:29:00+08:00
description: A把 $b$ 都提到最前面就好了。#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 = 200+5; char str[MAXN]; int cnt[26],n; int main(){ int T;scanf("%d",&T); while(T--){ CLR(cnt,0);scanf("%d",&n); scanf("%s",str+1); FOR(i,1,n) ++cnt[str[i]-'a']; FOR(i,1,cnt[1]) putchar('b'); FOR(i,0,25){ if(i == 1) continue; FOR(j,1,cnt[i]) putchar('a'+i); } puts(""); } return 0; }B我们证明答案一定 $\leq 1$：假设答案 $\geq 2$，考虑最后一步和倒数第二步，倒数第二步会把最后一步操作的点直接拉过来，所以最后一步的操作是无效的，可以删去。#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 = 100+5; int n,x[MAXN],y[MAXN],k; inline void Solve(){ scanf("%d%d",&n,&k); FOR(i,1,n) scanf("%d%d",x+i,y+i); FOR(i,1,n){ int mx = 0; FOR(j,1,n) mx = std::max(mx,std::abs(x[i]-x[j])+std::abs(y[i]-y[j])); if(mx <= k){ puts("1"); return; } } puts("-1"); } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }C1感觉比较难。。发现三个相邻的点 $i+j \bmod 3$ 两两不同，于是按照 $i+j \bmod 3$ 分类，找一个最小的将其全部翻转即可。C2会了 C1 稍微想想就会了。我们现在把 X 分成三类 $x_0,x_1,x_2$，把 O 分成三类 $o_1,o_2,o_3$，显然我们只需要选一对 $p \neq q$，将 $x_p$ 全都变为 O，并且将 $x_q$ 全都变为 X，可以得到这样是 $\leq \frac{1}{3}$ 的。#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.beg…

AGC038 部分题解
type: item
date: 2020-11-20T15:38:00+08:00
description: E题意有一个随机数生成器，生成 $[0,n-1]$ 之内的数，生成第 $i$ 个数的概率为 $\frac{A_i}{S}$，其中 $S=\sum_{i=1}^n A_i$。当 $\forall i \in [0,n-1]$ $i$ 被生成至少 $B_i$ 次时停止生成，求期望生成次数，对大质数取模。题解设第 $i$ 个数最后一次被随机到的时间为 $t_i$，答案就是 $\max t_i$ 的期望。限制所有都要完成一般都不好做，考虑 $min-max$ 容斥变成枚举一个集合 $S$ ，求 $\min_{i \in S} t_i$ 的期望。枚举集合后，问题变成求存在 $S$ 内某一个元素被随机 $b_i$ 次这个事件发生的期望时间。我们发现这样还是有可能随机到 $S$ 外的元素的，一个经典套路是算出期望多少次能操作一次 $S$ 内的元素，然后转化为只考虑 $S$ 内元素操作的问题，最后乘上去即可。可以发现这个期望次数为 $\frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i}$。现在问题在于给定一个集合 $S$ ，在 $S$ 内随机，求存在一个数满足条件的期望时间。首先根据：$$ \sum_{i \geq 0} P[X=i]i = \sum_{i \geq 0} P[X \geq i] $$可以得到，我们只需要对于每个时间 $T$ 求出在 $T$ 时间还没结束的概率，求和即可。我们考虑如何暴力的计算：先枚举在时间 $T$ 结束，接下来枚举序列 $b_i$ 表示集合中元素 $i$ 被随机到的次数，需要满足 $\forall i \in S,b_i < B_i$，$\sum_{i \in S} b_i = T$，这样一个序列的概率就是 $\prod_{i \in T} (\frac{A_i}{\sum_{i \in S} A_i})^{b_i}\frac{T!}{\prod_{i \in S} b_i!}$。所以答案是：$$ \sum_{S \subseteq [n],S \neq \emptyset} (-1)^{|S|-1}\frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i} \sum_{T=0}^{\sum_{i \in S} (b_i-1) + 1} \sum_{\{b\},\sum_{i \in S} b_i = T} \prod_{i \in T} (\frac{A_i}{\sum_{i \in S} A_i})^{b_i}\frac{T!}{\prod_{i \in S} b_i!} $$稍加整理可得$$ \sum_{S \subseteq [n],S \neq \emptyset} (-1)^{|S|-1} \frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i} \sum_{T=0}^{\sum_{i \in S} (b_i-1) + 1} T!(\frac{1}{\sum_{i \in S} A_i})^T \sum_{\{b\},\sum_{i \in S} b_i = T} \prod_{i \in S} \frac{A_i^{b_i}}{b_i!} $$于是可以考虑对这个 dp：发现最终答案系数只和 $\sum b_i,\sum A_i$ 有关，我们带着容斥系数 dp，设 $f_{i,j,k}$ 表示考虑前 $i$ 个数，$\sum b_i = j,\sum A_i = k$ 的答案，转移的时候枚举这个位置选或者不选，选的话枚举 $b_i$ 是多少，可以得到转移式子：$$ f_{i,j,k} = f_{i-1,j,k}-\sum_{x=0}^{B_i-1}\frac{A_i^x}{x!} f_{i-1,j-A_i,k-x} $$然后最后把应该乘的系数乘上去就好了。假设 $n,\sum A,\sum B$ 同阶，看起来时间复杂度是 $O(n^4)$ 的，但是实际分析一下：复杂度是：$$ \begin{aligned} \sum_{i=1}^n \sum_{j=0}^{\sum A_i} \sum_{k=0}^{\sum B_i } \sum_{l=0}^{B_i-1} 1 &= \sum_{i=1}^n \sum_{l=0}^{B_i-1} (\sum A_i) (\sum B_i)\\ &=(\sum A_i)(\sum B_i)^2 \\ &= O(n^3) \end{aligned} $$所以可以通过此题。代码可能和博客定义的是反的，感性理解一下（#include <bits/stdc++.h> #define fi first #define se second #define db double #defi…

20zr联赛集训day17
type: item
date: 2020-11-03T21:13:00+08:00
description: B 被降智了，所以掉分了。A考虑将这个串拆成三部分考虑：114，5，14。设 $f_{i,j}$ 表示 114 的 $4$ 的位置是 $i$，1 代表 $j$ 的方案数，$g_{i,j}$ 表示 14 中 1 的位置是 $i$，4 代表 $j$ 的方案数，另外记录一个 $s_{i,j}$ 表示前 $i$ 个字符中 $j$ 的数量，字符串是 $a$，那么答案是：$$ \sum_{i < j} f_{i,a_j}\times g_{j,a_i} \times (j-i-1-(s_{j-1,a_i}-s_{i,a_i})-(s_{j-1,a_j}-s_{i,a_j})) $$我们考虑将这个式子拆成可以分开维护的形式：$$ \begin{aligned} \sum_{i < j} f_{i,a_j}\times g_{j,a_i} \times(j-1-s_{j-1,a_i}-s_{j-1,a_j})\\ +\sum_{i < j} f_{i,a_j}\times g_{j,a_i} \times(-i+s_{i,a_i}+s_{i,a_j})\\ \end{aligned} $$我们枚举 $i$ 和 $a_j$，维护对应的 $\sum g_{j,a_i}\times (j-1-s_{j-1,a_i}-s_{j-1,a_j})$ 和 $\sum g_{j,a_i}$ 即可。可以用一些滚动数组技巧做到空间 $O((\Sigma) ^2)$。放个卡完空间的代码：#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 = 5e5 + 5; const int ha = 114514; char str[MAXN]; int n; inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } int sm1[26][26],sm2[26][26]; int smf[26],smg[26]; int main(){ scanf("%s",str+1);n = strlen(str+1); auto f = [&](int i,int j){ return str[i]-'a' == j ? 0 : (1ll*smf[j]*(smf[j]-1)/2)%ha; }; auto g = [&](int i,int j){ return str[i]-'a' == j ? 0 : smg[j]; }; int ans = 0; FOR(i,1,n-1) add(smf[str[i]-'a'],1); ROF(i,n,1){ FOR(j,0,25){ if(str[i]-'a' == j) continue; add(ans,1ll*f(i,j)*sm2[j][str[i]-'a']%ha); int coe = (smf[j]+smf[str[i]-'a']+1-i+ha)%ha; coe = 1ll*coe*f(i,j)%ha; add(ans,1ll*coe*sm1[j][str[i]-'a']%ha); } FOR(j,0,25){ add(sm1[str[i]-'a'][j],g(i,j)); int coe = (i-1-smf[j]-smf[str[i]-'a']+ha+ha)%ha; add(sm2[str[i]-'a'][j],1ll*g(i,j)*coe%ha); } if(i-1) add(smf[str[i-1]-'a'],ha-1); add(smg[str[i]-'a'],1); } printf("%d\n",ans); return 0; }B这个题没有括号！！表达式求值没有括号要考虑按照某个运算分成若干块处理。我们按照或运算将表达式分成很多段，每一段都是一堆与运算拼起来的，对于每一…

20zr联赛集训day15
type: item
date: 2020-11-03T20:56:00+08:00
description: A打表可以发现 $k>1$ 先手必胜，$k=1$ 取决于 $n$ 的奇偶性。具体证明：考虑如果 $n$ 是奇数的话，先手第一步取中间的那一块，序列变成了互相独立的两部分，之后先手只需要在没有被后手操作的块里模拟后手动作即可。如果 $n$ 是偶数的话，$k>1$ 也可以类似的划分成两段长度相等的段。$k=1$ 等价于每次只能取一个，所以 $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 int main(){ int n,k;scanf("%d%d",&n,&k); puts(k==1&&(!(n&1)) ? "yrrebxaw":"qjd"); return 0; }B求出每个边的存活时间，线段树分治即可，写个支持撤销的并查集。#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 = 1e5 + 5; const int ha = 1e9 + 7; int f[MAXN],sz[MAXN],inv[MAXN],now = 1; inline int find(int x){ return x == f[x] ? x : find(f[x]); } struct Node{ int x,y,z; Node(int x=0,int y=0,int z=0) : x(x),y(y),z(z) {} }; std::vector<Node> opt; inline void merge(int x,int y){ x = find(x);y = find(y); if(x == y) return; if(sz[x] > sz[y]) std::swap(x,y); now = 1ll*now*inv[sz[x]]%ha; now = 1ll*now*inv[sz[y]]%ha; opt.pb(Node(x,y,sz[x])); sz[y] += sz[x];f[x] = y; now = 1ll*now*sz[y]%ha; } inline void undo(){ Node v = opt.back();opt.pop_back(); now = 1ll*now*inv[sz[v.y]]%ha; f[v.x] = v.x;sz[v.x] = v.z;sz[v.y] -= v.z; now = 1ll*now*sz[v.x]%ha; now = 1ll*now*sz[v.y]%ha; } std::vector G[MAXN<<2]; #define lc ((x)<<1) #define rc ((x)<<1|1) inline void modify(int x,int l,int r,int L,int R,P d){ if(l == L && r == R){ G[x].pb(d); return; } int mid = (l + r) >> …

20联赛集训day13 题解
type: item
date: 2020-10-28T20:10:00+08:00
description: A. 异或考虑第 $i$ 位的贡献，发现每 $2^i$ 个数才会变化一次，所以答案是 $\sum_{i \geq 0} \lfloor\frac{n}{2^i}\rfloor $。考场上降智了，写了个枚举前缀卡到哪里算剩余贡献的垃圾做法。。#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 MAXM = 60; LL f[MAXM+1],pw[MAXM+1]; int main(){ pw[0] = 1;FOR(i,1,MAXM) pw[i] = pw[i-1]<<1; LL n;scanf("%lld",&n); FOR(i,1,MAXM){ FOR(j,0,i){// 结尾有多少个 1 f[i] += 1ll*(j+1)*pw[std::max(0,i-j-1)]; } } LL ans = 0; ROF(i,MAXM,0){ if(!((n>>i)&1)) continue; ans += f[i]; } if(n&1) ans++; printf("%lld\n",ans); return 0; } // [0,n-1] 偶数贡献 1 奇数贡献末尾连续 1 数量+1B.先考虑 $n=2$ 怎么做：我们设 $f_{a,b}$ 表示剩 $a$ 个颜色 $1$，$b$ 个颜色 $2$ 的答案是什么。我们设放在颜色 $1$ 上的钱为 $x$，颜色 $2$ 上的必然为 $1-x$，所以能得到的钱是 $\min(2xf_{a-1,b},2(1-x)f_{a,b-1})$。能解出来 $x=\frac{f_{a,b-1}}{f_{a-1,b}+f_{a,b-1}}$，也就是有方程 $f_{a,b} = \frac{2f_{a-1,b}f_{a,b-1}}{f_{a-1,b}+f_{a,b-1}}$。那么我们设 $g_{a,b} = f_{a,b}2^{a+b}$，有转移方程 $g_{a,b} = \frac{g_{a-1,b}g_{a,b-1}}{g_{a-1,b}+g_{a,b-1}}$，考虑两边取倒数，也就是$$ \frac{1}{g_{a,b}} = \frac{g_{a-1,b}+g_{a,b-1}}{g_{a-1,b}g_{a,b-1}} = \frac{1}{g_{a-1,b}}+\frac{1}{g_{a,b-1}} $$我们发现 $\frac{1}{g_{a,b}}$ 实际上是从 $(0,0)$ 走到 $(a,b)$ 的方案数，也就是 $\binom {a+b}{a}$。这样就能通过 $n=2$ 的部分。$n>2$ 的部分：我们考虑写出类似的状态：也就是有 $n$ 维。这个倒数也等价于从 $(0,0,\ldots,0)$ 走到 $(a_1,a_2,\ldots,a_n)$ 的方案数，也就是 $\binom{\sum_i a_i}{a_1,a_2,\ldots,a_n}$，所以答案就是 $\frac{n^{\sum_i a_i}}{\binom{\sum_i a_i}{a_1,a_2,\ldots,a_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…

contest5 题解
type: item
date: 2020-10-22T22:13:37+08:00
description: A. 星际穿越感觉也很神。。先将询问拆成前缀和的形式，我们要对于一组询问 $(l,r)$ 求出 $[l,r]$ 内所有点到 $r$ 的最短距离的和。考虑 $r$ 往左走的最短路径是怎么走的：引理一：往右走之前一定不会往左走反证法。如果先往左走在往右走，那么这个右边的点一定能 cover 到起点，所以可以第一步就先往右走，答案不会变劣。引理二：不会存在连续的两次往右走反证法。如果存在两次连续的往右走，那么之后一定有一次往左走，并且跨越起点的，我们可以一开始就走到这个点，答案不会变劣。所以我们的路径只有可能是先往右最多走一次，再往左走。我们观察一下一个点 $v$ 到达左边的点 $x$ 的最短距离的分布是怎么样的：如果 $dis(v,x)=1$，那么有 $l_v \leq x$。如果 $dis(v,x) \leq 2$，那么我们就会先走一步，用这个点中转，也就是问在区间 $[l_v,n]$ 内是否存在点 $y$，使得 $dis(x,y) \leq 1$。注意这里这个区间包含了一些根本不跨过 $v$ 的点，但这是显然不影响答案的。归纳可以得到：如果 $dis(v,x) \leq k$，当且仅当存在一个点 $y \in [l_v,n]$，满足 $dis(x,y) \leq k-1$。所以一个暴力的想法是每次先特判了距离为 $1$ 的点，然后每次求出最往左的距离为 $2$ 的点跳过去，以此类推。。对于跳这种东西，我们肯定想到要用倍增优化。我们想找到 $\leq k$ 的最往左的点，就要找到 $dis(x,y) \leq k-1$ 的最往左的点。。。所以我们定义在找 $dis(v,x) \leq k$ 的一次跳跃是从 $x$ 点找到最小的一个点 $z$，满足 $\exists y \in [l_v,n],dis(z,y) \leq k-1$，所以设 $f_{i,j}$ 表示从 $i$ 号点，跳了 $2^j$ 次（也就是处理了距离为 $[1,2^j+1]$ 的点），为了统计答案，设 $g_{i,j}$ 表示从 $i$ 号点跳了 $2^j$ 的所有答案，初始化 $f_{i,0} = \min_{j \geq i}\{l_j\}$，$f_{1,0} = 0,g_{i,0} = i-f_{i,0}$。转移大概写一下 ：$$ \begin{aligned} f_{i,j} &= f_{f_{i,j-1},j-1}\\ g_{i,j} &= g_{i,j-1}+g_{f_{i,j-1},j-1}+2^{j-1}(f_{i,j-1}-f_{i,j}) \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 const int MAXN = 3e5 + 5; const int MAXM = 18; int n,l[MAXN]; // 处理[i,n]跳2^j步的最远位置 和这一块的答案 int f[MAXN][MAXM+1]; LL g[MAXN][MAXM+1]; int pw[MAXM+1]; inline LL calc(int l,int p){ if(l > p) return 0; if(l >= ::l[p]) return p-l; LL res = p-::l[p],now = 1;p = ::l[p]; ROF(i,MAXM,0){ if(f[p][i] < l) continue; res += g[p][i] + now*(p-f[p][i]); now += (1<<i); p = f[p][i]; } if(l <= p) res += (now+1)*(p-l); return res; } inline LL gcd(LL x,LL y){ return !y ?…