https://atcoder.jp/contests/abc331

G - Collect Them All

n 卡

数字 1~m

写着i的有c[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的位置填入值的时候，可以计算和后面相比多少个，但是这里产生的分叉状态没法合并，意味着分叉的状态数量会影响时间空间复杂度

https://atcoder.jp/contests/abc329

G -  Delivery on Tree

n点，二叉树，根1

m 球, 每个球有 初始点 和 目标点

1个篮子 初始空，位置在1, 最大容量k

每次可以 移动篮子， 装入在起始位置的球，放出在目标位置的球，不能超过最大容量

最终篮子还要回到点1

问 有多少种路径方案方案，经过每条边恰好2次 mod 998244353，且所有球被移动到了目标位置

n 1e4

m 2e5

k 1e3

3s

1024mb

我的思路

2个关键性质：二叉树，所有边恰好走2次

对于一个二叉树的一个有分叉节点来说

如果有左侧向右侧的移动，那么 左侧先于右侧访问

如果有右侧向左侧的移动，那么 右侧先于左侧访问

如果同时有则方案为0

由上 我们可以知道一些 节点的左右的访问先后顺序

那么剩下的就是 点到祖先节点的移动，和祖先到后代的移动

对于 跨 lca的移动来说 可以拆分成 u->lca(u,v) 和 lca(u,v)->v

O(m log n) 可以完成

问题变成n点，2m条 下向上和上向下的 移动限制， 和部分节点有先后顺序的限制的合法方案数

一个问题是移动能否拆成单位距离1的移动？

注意到从上向下的时候 当遇到起始时，且边向内有目标点时，一定要拿起，而遇到放下时，优先放下更优，

而从下向上时， 离开的时候 拿起更优，而到终点时一定要放下

所以 把所有路径可以拆分成 很多单位距离为1的路径，并且同样的贪心规则向下的一定拿起，向上的第二次遇到拿起，能放下就放下，并且在限制了 左右先后以后 对于跨lca的需要注意的是，拿起时 是进入lca(u,v)->v方向的对应边的时候，而不是首次，而对于分叉的其实一样

所以稍微改一下，是进入边 和 离开边产生增加 和减少，不再放在点上

通过树上前缀和 可以 O(m+n)完成

所以变成n个点 有向但双向边，每个边有一个 进入增加，和离开减少，保持 <=k 的方案数

k 1e3 不算大

想法是dp[u][l/r] = map<inc,cnt> 是走这一侧合法的 增量集合? 能做吗？

AC倒是AC了就是写得有点久

https://ac.nowcoder.com/acm/contest/69791

F - 小辰刚学 gcd

https://ac.nowcoder.com/acm/contest/69791/F

长度n数组a

m个询问, 每次求query(l,r) = 集合{gcd(a[i..r]),i=l..r}的大小

范围

n 6e5

$a_i \in [1,2^{31}]$

1s

256MB

我的思路

显然 集合中的数 一定是 a[r] 的 因子，且两两互为倍数

所以 最多32个

然后我糊了一个st表+幂次查询，应该是 $O((n+m)\log(a_i)\log(n))$

TLE了

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=65524654

https://codeforces.com/contest/1893

n个 有色块, 第i个颜色$a_i$

安排它们到m个书架, 第i个书架 能放s_i个, $\sum s_{1\dots m} = n$

colorfulness(一个书架) = 该书架上同色块的最近距离(index差), 如果全部不同色则等于s_i

对于书架i有colorfulness下限di需求

提供摆放方案, 或者判断无法满足需求

m,n 2e5

3s

512mb

我的思路

下限的意思就是越大越好

确定了一个书架上放哪些块,那么????

好像一个书架上都没有什么想法

那就按照下限做, 先放个数最多的,然后它就按照下限要求放间隔

问题是 8容量,但是间隔下限要求3, wxyzwxyz是方案

但按照 下限要求 wxywxyzz 会卡住