311A TopCoder SRM555 XorBoard

简要题意

$n\times m$ 网格，至多做 $R$ 次行取反，至多做 $C$ 次列取反。求本质不同操作方案使得有 $S$ 个 $1$ ，本质不同指存在一行或一列操作次数不同。

网格大小 $1666$ 。

枚举最终被操作奇数次的行列，判断数量对不对，先乘个组合数，然后行上列上要算 $n$ 个无标号球放到 $m$ 个有标号盒子里的方案数，盒子可以为空，这个可以简单插板法计算。

（说实话当时没想到插板，写了个奇怪 dp，数数数少导致的）。

启示： 枚举操作是很笨且有效的手段，无标号计数可以考虑插板。

给一个长度为 $n$ 的字符串 $s_1,s_2$ ，字符集为 $3$ 。现允许 $s1$ 做 $1\to 2,2\to 3,3\to 1$ 的单向变换，代价为 $c_1,c_2,c_3$ ，求有多少操作序列代价和不超过 $w$ 使得 $s_1$ 变为 $s_2$ 。

考虑先把每个位置变换成与 $s_2$ 相同，然后就可以算出总操作次数，问题就变成了有若干个序列，每个序列对三取余长度限定，求这些序列归并成一个程度为 $m$ 的方案数。

这个问题可以直接上单位根反演的 EGF，然后暴力枚举展开式可以做到 $\mathcal{O}(n^6\log n)$ ，也可以当成多元生成函数求偏导优化 EGF 快速幂做到很低的复杂度。

不过显然也可以直接矩乘，因为发现操作到一定次数后所有序列长度都合法这个是充要的，那么直接设 $f_{i,j}$ 表示有 $i$ 个序列需要动零次， $j$ 个序列需要动一次，剩下动两次，直接转移，复杂度 $\mathcal{O}(n^6\log n)$ 。

给出 $n$ 种颜色的砖块，每种颜色有若干个，A 将这些砖块堆成若干个塔，要求每种颜色的砖块高度都相同，B 可以用任何一种颜色顺序依次取走这些砖，要求取走时这种颜色上不能有别的砖。

求有多少种本质不同的堆放方式，使得 B 的合法取走顺序数量在 $L,R$ 之间，两种方式本质不同当且仅当存在两个颜色 $x,y$ 在其中一种方案中 $x$ 在 $y$ 上方，而在另一种方案中 $x$ 不在 $y$ 上方。

$1\leq n\leq 6$

看到 $1\leq n\leq 6$ 和本质不同定义，考虑直接搜颜色之间偏序集，check 合法可以使用网络流，当然也可以使用霍尔定理节省代码量，最后直接算 B 的方案数是否合法。

搜偏序集也有讲究，一种最好写的方法是直接钦定每种颜色的高度，并且只在相邻的高度之间连边，在高度最低为 $1$ 时不难发现这样的偏序集都是本质不同的。

复杂度很大。

求有多少张 $n$ 个点 $k$ 条边的无向连通简单图满足前 $m$ 个点度数为 $2$ 。

$m=0$ 时就是图计数，经典做法枚举含根连通块大小直接 dp。

看上去 $m>0$ 时需要很多分类讨论，但是有一个神仙的观察：

对于一个度为二的点，可看作一条边上“长出了”一个点。

$m=1$ 我们直接枚举这个点是由哪条边长出来的，注意这个时候还有一种情况是将一条原来不可能出现的重边替换掉。

$m=2$ 也是类似的。

本文作者：World Creater

本文链接：http://worldcreaterwc.github.io/NFLS2024/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

最后更新：2024-12-19, 03:18:27

By World Creater.

随机文章回味旧文

博客信息

文章数目

13