专栏文章

计数乱刷

qqczrz6v4nhp6u
个人记录参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqjo96r
此快照首次捕获于
2025/12/04 05:54
3 个月前
此快照最后确认于
2025/12/04 05:54
3 个月前
查看原文
哎，我的计数真的是一坨翔。

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

考虑把矩阵看成一个有向图，则求 bb 次幂后为 00 矩阵当且仅当有向图不存在长度为 bb 的路径，所以说这就是对 DAG 的最长路求和。
那么直接开始分层做 DP。设 fi,j,0/1f_{i,j,0/1} 表示算了 ii 个点，最后一层有 jj 个点，方案数还是最长路总和。枚举这一层填了 kk 个，那么有
fi,j,0×(ai−ai−j)k×(i+kk)→fi,j,0fi,j,0×(ai−ai−j)k×(i+kk)→fi,j,1fi,j,1×(ai−ai−j)k×(i+kk)→fi,j,1f_{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(n3)O(n^3)。

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

设 aia_i 表示第 ii 行最小值，bjb_j 表示第 jj 列最小值，则显然有 f(x,y)=min⁡(ax,by)f(x,y)=\min(a_x,b_y)。
按值从大到小扫，设目前已经填了 ii 行 jj 列，加入一个值 vv 时有 xx 行 yy 列满足 a=v,b=va=v,b=v，则首先有贡献 (n−ix)(m−jy)v(i+x)(j+y)−ij{n-i\choose x}{m-j\choose y}v^{(i+x)(j+y)-ij}。
然后算方案数，发现除了 ≥\ge 还有 == 的限制，考虑容斥。指定有 pp 行 qq 列满足 min⁡>v\min>v，则容斥系数为 (−1)p+q(-1)^{p+q}，方案数就是 (xp)(yq)(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){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(n7)O(n^7) 的优秀复杂度。
考虑优化。发现两维其实是独立的，那么交替转移（如 p→q→x→yp\to q\to x\to y）即可做到 O(n4)O(n^4)。

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

考虑每个题目可见或不可见时的限制。
  • 若第 ii 个题目可见，则在它前面的只有 [1,i)[1,i) 中可见的题目，后面的任意。做个背包乘上 2n−i2^{n-i} 即可。
  • 若第 ii 个题目不可见，则在它前面的是所有 [1,i)[1,i) 中可见的题目，以及 (i,n](i,n] 中可见的题目。前面的任意，做个背包乘上 2i−12^{i-1} 即可。

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

∑idis(i,pi)\sum_i{\rm dis}(i,p_i) 最大等价于每个 i→pii\to p_i 都经过了重心。
以重心 uu 为根，则限制相当于 uu 无限制，所有儿子子树内的点都不能连向这棵子树中的点。直接做没性质，考虑容斥有 ii 个点连向本身，转化为统计有多少种方案满足有恰好 ii 个点连向本身。设子树大小为 kk，则系数为 (ki)2i!{k\choose i}^2i!，做一个背包即可 O(n2)O(n^2)。

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

考虑不合法的条件。如果在第 dd 位上存在 ai,d=1,aj,d=0a_{i,d}=1,a_{j,d}=0（i<ji<j），且 [i,j][i,j] 中的第 [0,d)[0,d) 位存在不相等的位，那么这就是不合法的。
同时可以发现这也是充分的。现在考虑 DP，设 fm,nf_{m,n} 表示填了 mm 位，序列长度为 nn 的方案数。考虑转移：
  • 不存在逆序对。则序列即为 0000⋯11110000\cdots1111 的形式，这一共有 n+1n+1 种，fm,n×(n+1)→fm+1,nf_{m,n}\times (n+1)\to f_{m+1,n}。
  • 存在逆序对。则序列为 0001???⋯?011110001???\cdots?01111 的形式。设 1,01,0 的距离为 ii，考虑将中间的问号缩成一段，转移即为 fm,n×(n−i+1)×2i−2→fm+1,n−i+1f_{m,n}\times (n-i+1)\times 2^{i-2}\to f_{m+1,n-i+1}。
前缀和优化即可做到 O(n2)O(n^2)。

ABC213G（思考：5min，代码：？）

n≤17n\le 17，考虑直接状压。设 fSf_S 表示 11 所在连通块恰好为 SS 的方案数（不考虑 SS 以外的连边情况），再设 gSg_S 表示 SS 的导出子图的边数。由于【连通】不好刻画，经典地使用容斥。枚举在 11 连通块内的是哪些点，有转移
fS=2gS−∑T⊆S,T≠S∧T≠∅fT2gS∖Tf_S=2^{g_S}-\sum_{T\subseteq S,T\ne S\land T\ne \varnothing}f_T2^{g_{S\setminus T}}
最后统计答案时考虑 SS 以外的贡献（即 2gU∖S2^{g_{U\setminus S}}）即可，复杂度 O(3n)O(3^n)。
可以使用集合幂级数的半在线卷积优化到 O(n22n)O(n^22^n)。

ABC134F（思考：10min，代码：？）

鉴定为灵感题，想到转化就是水题了。
考虑将排列视为二分图的一个完美匹配，其中 ii 连向 jj 的边权值位 ∣i−j∣|i-j|。考虑 DP：设 fk,i,vf_{k,i,v} 表示当前考虑了 1∼k1\sim k 的所有点，左右分别有 ii 个点没有匹配，当前权值为 vv，转移显然。复杂度 O(n4)O(n^4)。

ARC190D（思考：INF，代码：？）

观察到重要结论：∑i=1p−1ik≡−[(p−1)∣k](modp)\sum_{i=1}^{p-1}i^k\equiv-[(p-1)|k]\pmod p。证明：
设 gg 为 pp 的一个原根，则 g0,g1,⋯ ,gp−2g^0,g^1,\cdots,g^{p-2} 恰好取遍 1,2,⋯ ,p−11,2,\cdots,p-1。所以原式即为 ∑i=0p−2gik\sum_{i=0}^{p-2}g^{ik}，运用等比数列求和公式分讨一下即可。
将每一个为 00 的位置看作一个未知数并暴力把他们做 pp 次幂，有贡献的项必然满足所有未知数的指数  mod (p−1)=0{}\bmod (p-1)=0。剩下的 work 就轻松很多了。将其转化到图上考虑，那么一项就对应图上的一条路径。对 Ai,jA_{i,j} 有贡献的路径有且仅有如下几种：
  • p=2p=2，此时所有路径均合法。
  • p=3p=3，且路径形如 i→j→i→ji\to j\to i\to j，此时 Ai,jA_{i,j} 项次数为 2=p−12=p-1。
  • 路径形如 i→i→⋯→ji\to i\to \cdots \to j，此时 Ai,iA_{i,i} 项次数为 p−1p-1。
  • 路径形如 i→⋯→j→ji\to \cdots \to j\to j，此时 Aj,jA_{j,j} 项次数为 p−1p-1。
将原 AA 快速幂，再分讨一下即可算 00 的贡献即可。注意要乘上其他 00 任意选的方案数。
这个结论应该可以做一些比较神秘的反演题，不过局限性可能比较强。

AGC043D（思考：15min，代码：？）

注意到这个形式类似对 nn 个长度为 33 的排列做归并，考虑分析每个排列的形式。
不难发现若一个排列 A1,A2,A3A_1,A_2,A_3 中，若 Ai>Ai+1A_i>A_{i+1}，那么 Ai+1A_{i+1} 必然紧跟在 AiA_i 后面被选中。于是若结果序列 PP 中 Pi<max⁡j=1iPjP_i<\max_{j=1}^{i}P_j 就将 ii 向 i−1i-1 连一条边，如果存在连通块的大小 >3>3 则这个 PP 是不合法的，若大小为 22 或 33 的连通块个数 >n>n 也是不合法的。除此之外都是合法的，构造只需要贪心匹配即可。
现在开始 dp。设 fi,jf_{i,j} 表示填到了 PP 的第 ii 个位置，大小为 22 或 33 的连通块个数为 jj 的答案。转移枚举当前的连通块，乘上对应的二项式系数即可，复杂度 O(n2)O(n^2)。

ABC386G（思考：INF，代码：？）

计数差分序列。
考虑这样一个事情：
val(T)=(∑i=1mc(Ti))−m+n−1val(T)=\Big(\sum_{i=1}^mc(T_i)\Big)-m+n-1
其中 val(T)val(T) 表示 TT 的 MST 权值和，c(T)c(T) 表示 TT 的连通块数，TiT_i 表示只保留 TT 中权值 ≤i\le i 的边后形成的图，−m-m 是因为求和中每一个都要 −1-1，+n−1+n-1 是因为每条边都少算了一次。证明考虑换一个角度贡献即可。
有了这个做计数就轻松很多了。将求和与常数分开考虑，常数部分显然是简单的，现在考虑求和部分。
枚举保留的权值为 ≤k\le k，那么相当于对所有图的连通分量个数计数，其中一条边有 kk 的方案连上，有 m−km-k 的方案不连。枚举连通块的大小，则所有 c(Tk)c(T_k) 对总答案的贡献即为
∑i=1n(ni)(m−k)i(n−i)m(n−i2)fi\sum_{i=1}^n{n\choose i}(m-k)^{i(n-i)}m^{n-i\choose 2}f_i
其中 fif_i 表示形成大小为 ii 的连通图的方案数。
这就是经典问题了，将总方案减去不合法方案，枚举 11 号点所在连通块大小容斥即可。转移为
fi=m(i2)−∑j=1i−1(i−1j−1)(m−k)j(i−j)m(i−j2)fjf_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(n2m)O(n^2m)。也可以使用 exp⁡\exp 与 ln⁡\ln 的组合意义得到 O(nmlog⁡n)O(nm\log n) 或更低的做法。

AGC070B（思考：INF，代码：？）

深刻计数题，知道了最关键的 Hint 仍然没头绪的那种。话说这场全是神人题吧。
设 c0,c1c_0,c_1 分别表示偶环数与奇环数，考虑怎么算 2c12^{c_1} 的权值。一种思想是将 CkC^k 的权值拆成 ∑i=0k(ki)(C−1)i\sum_{i=0}^k{k\choose i}(C-1)^i，然后转化成【指定 ii 个结构，每个结构权值为 C−1C-1】的问题。那我们可以转化成【指定 ii 个奇环，每个奇环权值为 11】的问题。
然后你发现它直接指定不了啊，那我们考虑继续容斥。将条件改成【指定 ii 个环，其中有 00 个偶环】，那么【有 00 个偶环】的条件就等价于 [c0=0]=0c0[c_0=0]=0^{c_0}，故技重施，我们给偶环赋上 −1-1 的权值，这样就可以比较好地表示出原问题的答案。
现在的限制就是【指定 ii 个环，每个环的权值为 (−1)len−1(-1)^{len-1}】，以及【环中不能出现任意一个 i→pii\to p_i】。最后一个限制比较神秘，我们考虑忽略它怎么搞。设 SS 表示指定的环包含的点的集合，那么 SS 以外的贡献就是 (n−1)n−∣S∣(n-1)^{n-|S|}（若 1∉S1\notin S）或 n(n−1)n−∣S∣−1n(n-1)^{n-|S|-1}（若 1∈S1\in S），我们考虑 SS 内部的贡献。显然只跟 ∣S∣|S| 有关，设其 EGF 为 F(z)F(z)，并将单个置换环的系数的 EGF 设为 G(z)G(z)。那么有：
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)$。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...