https://atcoder.jp/contests/abc334

G - Christmas Color Grid 2

h x w 地图上0/1

4邻的1为连通块

求等概率把一个1改成0以后 exp(连通块个数) mod 998244353

h,w 1000

2s

1024mb

我的思路

就是找 去掉点后是否还连通，tarjan的算法

然后写出问题了

https://atcoder.jp/contests/abc333

G - Nearest Fraction

给一个(0,1)之间,不超过18位的小数r

求 一个分母<= N的最接近它的分数，如果有多个则输出最小的

n 1e10

2s

1024mb

我的思路

首先r肯定是通过字符串读取变成 整数/10的幂次

然后可以用 连分数的形式展开它

问题是这样的截断连分数因为分母<= N的限制 似乎直接截断不是最优的，二分最后一个位置的值？

例如样例$0.45, N = 5$

$\displaystyle 0.45=\frac{45}{100}=\frac{9}{20}=0+\frac{1}{\frac{20}{9}}=0+\frac{1}{2+\frac{1}{\frac{9}{2}}}=\frac{9}{20}=0+\frac{1}{\frac{20}{9}}=0+\frac{1}{2+\frac{1}{4+\frac{1}{2}}}$

这里 的 连分数是$[0,2,4,2]$

截断的话会是$\frac{1}{2},\frac{9}{4}$ 之间

而最优是$\frac{2}{5} = [0,2,2]$

所以想法是在会超过的地方 做个除法

然而 比较小数C++精度不够，用分数比较 longlong也会overflow

所以直接换语言，上python, 一次性过了

https://atcoder.jp/contests/abc332

G - Not Too Many Balls

n 种颜色的球，颜色i有ai个

m个盒子，第j个盒子最多放bj个球

此外 对于$(i\in[1,n],j\in[1,m])$, 盒子j最多放颜色i的球ij个

问所有盒子放的球的最大个数

n 500

m 5e5

ai,bj [0,1e12]

3s

1024mb

我的思路

这看起来就是 n个点表示颜色，m个点表示盒子

s->球，容量为ai表示这个颜色球最多这么多

球i->盒子j, 容量ij表示 (i,j)的限制

盒子->T 容量bj, 表示每个盒子的限制

这样flow(S,T)的值就是要求的结果

但是问题是 500*5e5 = 2.5e8 感觉会tle?

换一个角度如果把S,T去掉直接变成点分裂，那就是二分图最大匹配

二分图最大匹配从 过程的观点来看，就是有“反悔”的操作

https://atcoder.jp/contests/abc331

G - Collect Them All

n 卡

数字 1~m

c[i]张卡 写着i

随机 抽取一个卡, 记录抽过的卡, 放回箱子

求 exp(次数) 直到每种数字至少被抽到一次, mod 998244353

m <= n <= 2e5

2s

1024mb

我的思路

这 看起来是 min-max 容斥吗？

对于一个具体的方案，有对应的集合$S=\lbrace t_1,t_2,\cdots,t_m \rbrace$ 表示每个元素首次发生的次数

那么$\max(S)$就是 完成的时刻

$\max(S)=\sum_{T\subseteq S}(-1)^{|T+1} \min(T)$

$E(\max(S))=E(\sum_{T\subseteq S,T\neq \emptyset}(-1)^{|T|+1} \min(T))=\sum_{T\subseteq S}(-1)^{|T|+1} E(\min(T))$

$E(\min(T)) = \sum_{t=1}^{\infty} p(\min(T)=t)$

也就是 t-1次没有选中T内的任何一个,而第t次选中了

设选中的概率 为$\displaystyle p_T = \frac{\sum_{i\in T} c_i}{N}$

$E(\min(T)) = \sum_{t=1}^{\infty} tp(1-p)^{t-1}= -p(\sum_{t=1}^{\infty}(1-p)^t)’$, 把p看作一元变量

$=-p((1-p)\frac{1}{1-(1-p)})’$

$=-p((\frac{1}{p}-1)’$

$=\frac{1}{p}$

$\displaystyle \mathrm{ans}=\sum_{T\subset S} (-1)^{|T|+1} \frac{N}{\sum_{i\in T}c_i}$

所以如果能求得 所有$\lbrace 1,2,\cdots,m \rbrace$子集的$c_i$和 对应的$(-1)^{|T|+1}$ 就好了

因为$c_i$和是小于N的

注意到 $\displaystyle -(1-x^{sz_1})(1-x^{sz_2})\cdots(1-x^{sz_m})$的系数，就是要求的内容

https://atcoder.jp/contests/abc330

G - Inversion Squared

a[n]

$a[i] \in [1,n]$ 或$a[i]=-1$, 1~n最多出现一次

-1能替换成$[1\cdots n]$中的数

求 所有 ((a能产生的$1\dots n$排列)的逆序对的个数)的平方和，mod 998244353

n = 3000

2s

1024mb

我的思路

题面很质朴，n 3000说明可能n^2一类的算法

令x=-1的个数

对于非-1的部分可以直接算出，然后乘上 (x)! 就是贡献了

对于-1和-1之间，要知道每一个 排列的方案，交换这两个位置 对应的也是一个方案，而这两个方案之间 一个贡献1,一个贡献0

所以 是 $x!\frac{(x-1)x}{2}\cdot \frac{1}{2}$, 分别是 总方案数，配对位置数，和1/2的平均贡献

那么这个问题来到的就是 -1和给定值之间的逆序对 的贡献个数了

contribute[有值pos1] = f_left(value,left -1 count) + f_right(value, right -1 count)

所以 如果能 计算出

$f(value,cnt)=$ 在一共x个-1的情况下，左侧-1的位置有cnt个，当前值是value,的方案数

l[v] = 比v小的未填的值的个数

那么左侧的贡献为 $cnt\star (x-l[value]) (x-1)!$

右侧的贡献为 = $(x-cnt)\star lvalue!$

似乎就没了吧？

xxxxxxxxxxxxxxxxxx上面读错题目了， 要逆序对个数 的平方和，不只是逆序对的个数和

已经填好的逆序对=C，-1内部的逆序对=A，-1和填好的逆序对=B

$(C+A+B)^2=C^2+A^2+B^2+2AB+2BC+2CA$

首先C是不变的，A,B是根据填写情况变化的

所以这里的$C^2+2BC+2CA$很好算，和上面一样，

那问题来到$A^2,B^2,2AB$怎么算

一个想法是和上面一样，考虑两个位置交换会对贡献有什么影响

显然一样的， 交换2个位置，那么它们的A相差为1,问题是B是可能变化的，且变化无法确定

A^2 也有办法，因为A^2相当于x个数的全排列的 逆序对平方和

1
2
3
4

len=1:0
len=2:0 [1]
len=3:0  1 [1  2][2  3]
len=4:0  1  1  2  2  3 [1  2  2  3  3  4][2  3  3  4  4  5][3  4  4  5  5  6]

个数上可以 生成函数表示

$f_0(x)=1$

$f_1(x)=1+x=(1+x)f_0(x)$

$f_2(x)=1+2x+2x^2+x^3=(1+x+x^2)f_1(x)$

$f_3(x)=(1+x+x^2+x^3)f_2(x)$

这个 采取 分治的方法计算 $O(n^2 \log n)$ 可以算出来，但是 $2^{23} =8388608 > 4498500=\frac{2999\cdot 3000}{2}$ 这会炸掉吗？

然而这个思路带来的一个新的启发能否用 生成函数的方法 直接计算出每个逆序对的方案数，

例如 $f_3(x)=(1+x+x^2+x^3)f_2(x)$ 中$x^2$是 在说 对于后缀长度$4$的4个数字，第一个是其中第2+1小的（因为1-index所以+1),

想了想，好像并不行，虽然在-1的位置填入值的时候，可以计算和后面相比多少个，但是这里产生的分叉状态没法合并，意味着分叉的状态数量会影响时间空间复杂度