计数乱刷

· · 个人记录

哎，我的计数真的是一坨翔。

P11173（思考：？，代码：？）

考虑把矩阵看成一个有向图，则求 b 次幂后为 0 矩阵当且仅当有向图不存在长度为 b 的路径，所以说这就是对 DAG 的最长路求和。

那么直接开始分层做 DP。设 f_{i,j,0/1} 表示算了 i 个点，最后一层有 j 个点，方案数还是最长路总和。枚举这一层填了 k 个，那么有

f_{i,j,0}\times(a^{i}-a^{i-j})^k\times{i+k\choose k}\to f_{i,j,0}\\f_{i,j,0}\times(a^{i}-a^{i-j})^k\times{i+k\choose k}\to f_{i,j,1}\\f_{i,j,1}\times(a^{i}-a^{i-j})^k\times{i+k\choose k}\to f_{i,j,1}

复杂度 O(n^3)。

AGC039F（思考：？，代码：？）

设 a_i 表示第 i 行最小值，b_j 表示第 j 列最小值，则显然有 f(x,y)=\min(a_x,b_y)。

按值从大到小扫，设目前已经填了 i 行 j 列，加入一个值 v 时有 x 行 y 列满足 a=v,b=v，则首先有贡献 {n-i\choose x}{m-j\choose y}v^{(i+x)(j+y)-ij}。

然后算方案数，发现除了 \ge 还有 = 的限制，考虑容斥。指定有 p 行 q 列满足 \min>v，则容斥系数为 (-1)^{p+q}，方案数就是 {x\choose p}{y\choose q}(k-v)^{(n-i)(m-j)-(n-i-p)(m-j-q)}(k-v+1)^{(n-i-p)(m-j-q)-(n-i-x)(m-j-y)}。直接做可以得到 O(n^7) 的优秀复杂度。

考虑优化。发现两维其实是独立的，那么交替转移（如 p\to q\to x\to y）即可做到 O(n^4)。

P10143（思考：？，代码：？）

考虑每个题目可见或不可见时的限制。

ARC087F（思考：？，代码：？）

以重心 $u$ 为根，则限制相当于 $u$ 无限制，所有儿子子树内的点都不能连向这棵子树中的点。直接做没性质，考虑容斥有 $i$ 个点连向本身，转化为统计有多少种方案满足有恰好 $i$ 个点连向本身。设子树大小为 $k$，则系数为 ${k\choose i}^2i!$，做一个背包即可 $O(n^2)$。 ### AT_nomura2020_f（思考：？，代码：？） 考虑不合法的条件。如果在第 $d$ 位上存在 $a_{i,d}=1,a_{j,d}=0$（$i<j$），且 $[i,j]$ 中的第 $[0,d)$ 位存在不相等的位，那么这就是不合法的。 同时可以发现这也是充分的。现在考虑 DP，设 $f_{m,n}$ 表示填了 $m$ 位，序列长度为 $n$ 的方案数。考虑转移： - 不存在逆序对。则序列即为 $0000\cdots1111$ 的形式，这一共有 $n+1$ 种，$f_{m,n}\times (n+1)\to f_{m+1,n}$。 - 存在逆序对。则序列为 $0001???\cdots?01111$ 的形式。设 $1,0$ 的距离为 $i$，考虑将中间的问号缩成一段，转移即为 $f_{m,n}\times (n-i+1)\times 2^{i-2}\to f_{m+1,n-i+1}$。 前缀和优化即可做到 $O(n^2)$。 ### ABC213G（思考：5min，代码：？） $n\le 17$，考虑直接状压。设 $f_S$ 表示 $1$ 所在连通块恰好为 $S$ 的方案数（不考虑 $S$ 以外的连边情况），再设 $g_S$ 表示 $S$ 的导出子图的边数。由于【连通】不好刻画，经典地使用容斥。枚举在 $1$ 连通块内的是哪些点，有转移 $$f_S=2^{g_S}-\sum_{T\subseteq S,T\ne S\land T\ne \varnothing}f_T2^{g_{S\setminus T}}$$ 最后统计答案时考虑 $S$ 以外的贡献（即 $2^{g_{U\setminus S}}$）即可，复杂度 $O(3^n)$。 可以使用集合幂级数的半在线卷积优化到 $O(n^22^n)$。 ### ABC134F（思考：10min，代码：？） 鉴定为灵感题，想到转化就是水题了。 考虑将排列视为二分图的一个完美匹配，其中 $i$ 连向 $j$ 的边权值位 $|i-j|$。考虑 DP：设 $f_{k,i,v}$ 表示当前考虑了 $1\sim k$ 的所有点，左右分别有 $i$ 个点没有匹配，当前权值为 $v$，转移显然。复杂度 $O(n^4)$。 ### ARC190D（思考：INF，代码：？） 观察到重要结论：$\sum_{i=1}^{p-1}i^k\equiv-[(p-1)|k]\pmod p$。证明： 设 $g$ 为 $p$ 的一个原根，则 $g^0,g^1,\cdots,g^{p-2}$ 恰好取遍 $1,2,\cdots,p-1$。所以原式即为 $\sum_{i=0}^{p-2}g^{ik}$，运用等比数列求和公式分讨一下即可。 将每一个为 $0$ 的位置看作一个未知数并暴力把他们做 $p$ 次幂，有贡献的项必然满足所有未知数的指数 ${}\bmod (p-1)=0$。剩下的 work 就轻松很多了。将其转化到图上考虑，那么一项就对应图上的一条路径。对 $A_{i,j}$ 有贡献的路径有且仅有如下几种： - $p=2$，此时所有路径均合法。 - $p=3$，且路径形如 $i\to j\to i\to j$，此时 $A_{i,j}$ 项次数为 $2=p-1$。 - 路径形如 $i\to i\to \cdots \to j$，此时 $A_{i,i}$ 项次数为 $p-1$。 - 路径形如 $i\to \cdots \to j\to j$，此时 $A_{j,j}$ 项次数为 $p-1$。 将原 $A$ 快速幂，再分讨一下即可算 $0$ 的贡献即可。注意要乘上其他 $0$ 任意选的方案数。 这个结论应该可以做一些比较神秘的反演题，不过局限性可能比较强。 ### AGC043D（思考：15min，代码：？） 注意到这个形式类似对 $n$ 个长度为 $3$ 的排列做归并，考虑分析每个排列的形式。 不难发现若一个排列 $A_1,A_2,A_3$ 中，若 $A_i>A_{i+1}$，那么 $A_{i+1}$ 必然紧跟在 $A_i$ 后面被选中。于是若结果序列 $P$ 中 $P_i<\max_{j=1}^{i}P_j$ 就将 $i$ 向 $i-1$ 连一条边，如果存在连通块的大小 $>3$ 则这个 $P$ 是不合法的，若大小为 $2$ 或 $3$ 的连通块个数 $>n$ 也是不合法的。除此之外都是合法的，构造只需要贪心匹配即可。 现在开始 dp。设 $f_{i,j}$ 表示填到了 $P$ 的第 $i$ 个位置，大小为 $2$ 或 $3$ 的连通块个数为 $j$ 的答案。转移枚举当前的连通块，乘上对应的二项式系数即可，复杂度 $O(n^2)$。 ### ABC386G（思考：INF，代码：？） 计数差分序列。 考虑这样一个事情： $$val(T)=\Big(\sum_{i=1}^mc(T_i)\Big)-m+n-1$$ 其中 $val(T)$ 表示 $T$ 的 MST 权值和，$c(T)$ 表示 $T$ 的连通块数，$T_i$ 表示只保留 $T$ 中权值 $\le i$ 的边后形成的图，$-m$ 是因为求和中每一个都要 $-1$，$+n-1$ 是因为每条边都少算了一次。证明考虑换一个角度贡献即可。 有了这个做计数就轻松很多了。将求和与常数分开考虑，常数部分显然是简单的，现在考虑求和部分。 枚举保留的权值为 $\le k$，那么相当于对所有图的连通分量个数计数，其中一条边有 $k$ 的方案连上，有 $m-k$ 的方案不连。枚举连通块的大小，则所有 $c(T_k)$ 对总答案的贡献即为 $$\sum_{i=1}^n{n\choose i}(m-k)^{i(n-i)}m^{n-i\choose 2}f_i$$ 其中 $f_i$ 表示形成大小为 $i$ 的连通图的方案数。 这就是经典问题了，将总方案减去不合法方案，枚举 $1$ 号点所在连通块大小容斥即可。转移为 $$f_i=m^{i\choose 2}-\sum_{j=1}^{i-1}{i-1\choose j-1}(m-k)^{j(i-j)}m^{i-j\choose 2}f_j$$ 复杂度 $O(n^2m)$。也可以使用 $\exp$ 与 $\ln$ 的组合意义得到 $O(nm\log n)$ 或更低的做法。 ### AGC070B（思考：INF，代码：？） 深刻计数题，知道了最关键的 Hint 仍然没头绪的那种。话说这场全是神人题吧。 设 $c_0,c_1$ 分别表示偶环数与奇环数，考虑怎么算 $2^{c_1}$ 的权值。一种思想是将 $C^k$ 的权值拆成 $\sum_{i=0}^k{k\choose i}(C-1)^i$，然后转化成【指定 $i$ 个结构，每个结构权值为 $C-1$】的问题。那我们可以转化成【指定 $i$ 个奇环，每个奇环权值为 $1$】的问题。 然后你发现它直接指定不了啊，那我们考虑继续容斥。将条件改成【指定 $i$ 个环，其中有 $0$ 个偶环】，那么【有 $0$ 个偶环】的条件就等价于 $[c_0=0]=0^{c_0}$，故技重施，我们给偶环赋上 $-1$ 的权值，这样就可以比较好地表示出原问题的答案。 现在的限制就是【指定 $i$ 个环，每个环的权值为 $(-1)^{len-1}$】，以及【环中不能出现任意一个 $i\to p_i$】。最后一个限制比较神秘，我们考虑忽略它怎么搞。设 $S$ 表示指定的环包含的点的集合，那么 $S$ 以外的贡献就是 $(n-1)^{n-|S|}$（若 $1\notin S$）或 $n(n-1)^{n-|S|-1}$（若 $1\in S$），我们考虑 $S$ 内部的贡献。显然只跟 $|S|$ 有关，设其 EGF 为 $F(z)$，并将单个置换环的系数的 EGF 设为 $G(z)$。那么有： $$G(z)=\sum_{i\ge 1}(i-1)!(-1)^{i-1}\times\frac{z^i}{i!}\\ F(z)=\exp G(z)$$ 然后你惊奇地发现 $G(z)=\ln (1+z)$，所以说 $F(z)=1+z$，$S$ 有贡献当且仅当 $[|S|\le 1]$！！！ 现在我们再来考虑加上 $i\to p_i$ 限制的情况。对这个再做一次容斥，指定有哪些边被选入环中并带上 $(-1)^{|S|}$ 的贡献。不难发现这些边一定形成了若干条祖孙链，我们将这些链缩成点考虑，这就直接转化成了上述情况！！！换句话说，只有 $S$ 恰好为 $\le 1$ 个祖孙链的形式才会对答案有贡献。这已经是相当容易的一个问题了，分讨 $|S|=0/1$： - $|S|=0$。此时的贡献为 $n(n-1)^{n-1}$。 - $|S|=1$。算一下点数为 $k$，不包含 / 包含 $1$ 的祖孙链分别有 $s_{k,0/1}$ 条，那么贡献就是 $(\sum_{k}s_{k,0}(n-1)^{n-k})+(\sum_ks_{k,1}n(n-1)^{n-k-1})$。注意这里容斥奇偶环的系数与容斥 $i\to p_i$ 的系数抵消了。 做完了，复杂度 $O(n)$。总结一下： - 定义总权值为所有结构的权值之积，若出现【恰好有 $k$ 个结构，每个结构权值为 $C$】这样的限制，那么可以通过 $C^k=\sum_{i=0}^k{k\choose i}(C-1)^i$ 转化成【指定有 $k$ 个结构，每个结构的权值为 $(C-1)$】 的问题。如果是【这样的结构恰好有 $0$ 个】这样的限制，可以将其视为 $C=0$ 的情况。 - 看啥不顺眼就容斥啥，不要被容斥的层层嵌套吓住。 - 如果实在没头绪可以尝试表一下容斥系数。 ### P11746（思考：10min，代码：？） 套路题。 首先若 $2|(n+m)$ 显然无解，否则考虑计数完全相同的行/列有偶数个的情况。 此时奇数的权值为 $0$，偶数的权值为 $1$，根据经典技巧，算出【奇 $1$ 偶 $1$】与【奇 $-1$ 偶 $1$】的答案，相加后除以 $2$ 即可。 【奇 $1$ 偶 $1$】是好算的，即为总方案数 $2^{nm}$。考虑【奇 $-1$ 偶 $1$】，实际上就是将每一个完全相同的行的权值设为 $-1$，再对每一种方案的权值之积求和。根据上一题的经典结论，将【一种恰好有 $k$ 个合法结构的方案，权值为 $C^k$】转化为【指定 $k$ 个结构合法，权值为 $(C-1)^k$】。代入 $C=-1$，我们得到每一个相同的行/列权值为 $-2$。枚举有 $i$ 行 $j$ 列合法，开始计数。 - 若 $i=0\land j=0$：则贡献为 $2^{nm}$。 - 若 $i=0\land j>0$：则贡献为 ${m\choose j}(-2)^j\times 2^j\times 2^{n(m-j)}$。 - 若 $i>0\land j=0$：则贡献为 ${n\choose i}(-2)^i\times 2^i\times 2^{m(n-i)}$。 - 若 $i>0\land j>0$：则贡献为 ${n\choose i}{m\choose j}(-2)^{i+j}\times 2\times 2^{(n-i)(m-j)}$。 枚举 $i,j$ 并求和即可做到 $O(n^2)$。 考虑优化。瓶颈在于 $i>0\land j>0$ 的部分，推一下这边的式子： $$\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m{n\choose i}{m\choose j}(-2)^{i+j}\times 2\times 2^{(n-i)(m-j)}\\ =&~2\sum_{i=1}^n{n\choose i}(-2)^i\sum_{j=1}^m{m\choose j}(-2)^{j}\times 2^{(n-i)(m-j)}\\ =&~2\sum_{i=1}^n{n\choose i}(-2)^i\Big((2^{n-i}-2)^m-2^{m(n-i)}\Big) \end{aligned}$$ 可以使用光速幂的技巧做到 $O(n)$。 ### ABC389G（思考：5min，代码：？） 米共，懒得喷。 直接分层 dp：设 $f_{i,j,k,u,0/1}$ 表示目前已经选出了 $i$ 个点、$j$ 条边，偶减奇为 $k$，最后一层有 $u$ 个点的方案数。有转移： $$f_{i+v,j+w,k+v(-1)^{1-t},v,1-t}\gets f_{i,j,k,u,t}\times {i+v-1\choose v}\times {\rm coef}_{u,v,w}$$ 其中 ${\rm coef}_{u,v,w}$ 表示最后一层有 $u$ 个点，新加 $v$ 个点、$w$ 条边，且新加的点每一个都与最后一层有连边的方案数。枚举没有连边的点并容斥，那么有 $${\rm coef}_{u,v,w}=\sum_{i=0}^u{u\choose i}(-1)^i{u(v-i)+\frac{v(v-1)}{2}\choose w}$$ 最终的复杂度是 $O(n^8)$。记得刷表转移，并且如果当前状态没有值就 `continue` 掉。 ### P11893（思考：0s，代码：？） 神如金出题人，能把这种又唐又恶心的题放到 T4 这辈子有了。 我们直接可以得到答案的表达式 $$\Big(n![z^n](z{\rm e}^z-{\rm e}^z+1)^2({\rm e}^z-1)\Big)-\Big((n-1)![z^{n-1}]z{\rm e}^z(z{\rm e}^z-{\rm e^z}+1)({\rm e}^z-1)\Big)$$ 将上述式子展开成关于 $z$ 与 ${\rm e}^z$ 的多项式后可以直接得到通项，并且阶乘会被约成 $\le 2$ 次的下降幂。于是直接维护 $n\bmod (10^9+7)$ 与 $n\bmod (10^9+6)$ 算即可。 ### P11897（思考：5min，代码：？） 最开始看成可以选择一个维度并且选择一个点置成 $0$，调了大半天样例/xk 若两个点分别是 $a,b$，那么显然 $\bf B$ 赢的充要是 $2|{\rm popc}(a\cup b)$。单位根反演（？）一下可以得到 $[2|{\rm popc}(a\cup b)]=\frac 12\Big(1+(-1)^{{\rm popc}(a\cup b)}\Big)$，后面的部分就是一个类似 FWT 的东西，直接做可以做到 $O(qn2^k)$，然后类似线段树地每层排除掉无交或者被包含的区间即可做到 $O(q2^k)$。 ### AT_hhkb2020_f（思考：？，代码：？） 设 $F(x)={\rm Pr}[\max(X_i)\le x],P(x)={\rm Pr}[\max(X_i)=x]$，那么简单的推导有 $$P(x)=F'(x)$$ 原问题的答案即为 $$\int_0^{+\infty}xP(x){\rm d}x=\int_0^{+\infty}xF'(x){\rm d}x$$ 然后考虑 $F(x)$ 是什么。显然 $F(x)$ 可以表示为 $$F(x)=\prod_{i=1}^nf_i(x)$$ 其中 $$f_i(x)=\begin{cases}0&\text{if }x<l_i\\\dfrac{x-l_i}{r_i-l_i}&\text{if }l_i\le x<r_i\\1&{\rm otherwise}\end{cases}$$ 将 $l,r$ 离散化后可以将 $F(x)$ 表示为 $O(n)$ 段的分段函数，对于每一段分别做积分即可。扫描线维护 $F(x)$ 即可做到 $O(n^2)$。