A
设 \(f_{i,S}\) 表示考虑前 \(i\) 行,选出的矩形在第 \(i\) 行上形成 \(S\) 中的区间的方案数,
每行的 \(S\) 只有 \(O(2^m)\) 种,总复杂度 \(O(n2^{2m})\)。
B
考虑先修改再查询怎么做。
考虑左下角为 \((x_1,y_1)\),右上角为 \((x_2,y_2)\) 的矩形,发现斜率在 \(\left[\dfrac{y_1}{x_2},\dfrac{y_2}{x_1}\right]\) 内的向量会穿过它,
考虑扫描斜率,扫到 \(\dfrac{y_1}{x_2}\) 时加入这个矩形,扫到 \(\dfrac{y_2}{x_1}\) 时删除它,则扫到一个向量的斜率时已经加入了所有其能穿过的矩形。
考虑一个向量 \((\Delta x,\Delta y)\) 能穿过的、左下角在 \((x,y)\) 的矩形,则这个向量需要延伸 \(\max\left(\dfrac x{\Delta x},\dfrac y{\Delta y}\right)\) 倍才能碰到它,
要求向量碰到的第一个矩形,即要求向量能穿过的、\(\max\left(\dfrac x{\Delta x},\dfrac y{\Delta y}\right)\) 最小的矩形。
考虑分讨掉这个 \(\max\)。对于 \(\dfrac x{\Delta x}>\dfrac y{\Delta y}\iff\dfrac yx<\dfrac{\Delta y}{\Delta x}\) 的矩形,只需求 \(\dfrac x{\Delta x}\) 的最小值,也就只需求 \(x\) 的最小值,
对于 \(\dfrac x{\Delta x}<\dfrac y{\Delta y}\iff\dfrac yx>\dfrac{\Delta y}{\Delta x}\) 的矩形,只需求 \(\dfrac y{\Delta y}\) 的最小值,也就只需求 \(y\) 的最小值。
以 \(\dfrac yx\) 为下标对加入的所有矩形建权值线段树,维护区间 \(x,y\) 最小值即可。
然后这个题不是先修改再查询,套个 CDQ 变成先修改再查询即可。
C
选到每个鸽笼的概率会随着鸽笼的填满而变化,这个不太好处理,所以先用拒绝采样转化下题意:
每次可以选任意一个鸽笼,这个鸽笼满了就再选一个。记下每次选择的鸽笼作为操作序列。
考虑对 \(i\) 算答案。考虑容斥,把答案看成恰好 \(0\) 个鸽笼比 \(i\) 更晚填满的概率,
设 \(g(S)\) 表示钦定 \(S\) 中鸽笼比 \(i\) 更晚填满的概率,则答案为 \(\sum\limits_{S\in U-\{i\}}(-1)^{|S|}g(S)\)。
钦定 \(S\) 中鸽笼比 \(i\) 更晚填满,实际上就是操作序列上 \(S\) 中每个数都在 \(i\) 的最后一次出现后出现过,
也就是 \(\forall j\in S\),\(j\) 在 \(i\) 的最后一次出现前出现小于 \(a_j\) 次。
考虑只留操作序列中,\(i\) 的最后一次出现前的 \(i\) 以及 \(S\) 中的数,求满足条件的方案数除以总方案数。
\(i\) 比较特殊,必须出现 \(a_i\) 次,所以我们先不填 \(i\)。
设 \(f_x\) 表示当前在操作序列中填入 \(x\) 个数的方案数,每次对于一个 \(j\in S\) 考虑填入 \(k\) 个 \(j\),则有转移 \(f_x\gets f_{x-k}{x\choose k}(k<a_j)\),
填完长度为 \(x\) 的操作序列后,有 \({x+a_i-1\choose a_i-1}\) 种填 \(i\) 的方案(因为 \(i\) 的最后一次出现一定在最后),
所以在操作序列中填入 \(x+a_i\) 个数的满足条件的方案数为 \(f_x{x+a_i-1\choose a_i-1}\)。
而如果不需要满足条件,每个数都可以随便填,所以在操作序列中填入 \(x+a_i\) 个数的总方案数为 \((|S|+1)^{x+a_i}\),
所以 \(g(S)=\sum\limits_{x}\dfrac{f_x{x+a_i-1\choose a_i-1}}{(|S|+1)^{x+a_i}}\)。(\(x\) 不会很大,最多只有 \(a_i+\sum\limits_{j\in S}(a_j-1)\))
考虑同时计算大小相同的 \(S\) 的 \(g\) 值。设 \(f_{o,x}\) 表示除 \(i\) 外填入了 \(o\) 种数(即 \(|S|=o\)),且填入了 \(x\) 个数的方案数,
则有转移 \(f_{o,x}\gets f_{o-1,x-k}{x\choose k}(k<a_j)\)。
则答案为 \(\sum\limits_{S\in U-\{i\}}(-1)^{|S|}g(S)=\sum\limits_{o=1}^{n-1}(-1)^o\sum\limits_{|S|=o}g(S)=\sum\limits_{o=1}^{n-1}(-1)^o\sum\limits_{x}\dfrac{f_{o,x}{x+a_i-1\choose a_i-1}}{(|S|+1)^{x+a_i}}\)。
发现这个转移是背包的形式,所以一开始可以先把所有物品装进背包,求 \(i\) 的答案时把 \(i\) 拿出来。复杂度 \(O(n^5)\)。
D
最大值最小,考虑二分答案 \(k\)。
两个人至少有一个停在点上的那档部分分,直接设 \(f_{x,y}\) 表示可不可能一个人在 \(x\),一个人在 \(y\),BFS 转移即可。
但是他们可能停在边上。所以在每条边上加一个点,一个人在这个点上就代表他停在这条边上,然后就同上了。
转移时需要算点线距和线线距,合理利用点乘叉乘即可。
标签:dfrac,limits,第九次,sum,2024,Delta,矩形,CSP,鸽笼 From: https://www.cnblogs.com/5k-sync-closer/p/18449440