CCPC2021广州 Gym103415A Math Ball

Problem – A – Codeforces

题意:你有$n$种球,同种球没有区别,并且每种球都有无限个。

你可以拿一些球,如果第$i$种球拿了$k_i$个,那么你就会得到$\prod_i k_i^{c_i}$的价值。

求总共拿不超过$w$个球的所有方案的价值的总和。

$n \le 10^5,\;\sum_{i} c_i \le 10^5,\; w \le 10 ^ {18}$。


如果我们能得到关于选球个数的生成函数$F(x)$,那么$\frac {F(x)}{1 – x}$的$x^w$项的系数就是答案。

继续阅读“CCPC2021广州 Gym103415A Math Ball”

Gym103261C StalinSort Algorithm 优化DP

Problem – C – Codeforces

题意:你有一个斯大林排序算法,维护一个已排序序列,如果新加入的数仍然有序则不进行操作,否则可以毙掉新加的数或者序列里最后一个数,但是枪毙只能进行一次,如果毙掉原来的数后不满足有序则不能这样操作。

问对给定排列执行这个算法之后最少删除几个数,$n \le 5\times 10 ^ 5$。


不难看出加入一个新的数时只会和当前最后一个数有关系,所以可以维护一个DP数组$dp_i$表示以$i$结尾时最多保留几个数,那么如果$i<j$且$dp_i$可以转移到$dp_j$,则说明$i$和$j$可以共存于最后的序列中。

考虑如何维护这个东西。

继续阅读“Gym103261C StalinSort Algorithm 优化DP”

GP of Korea Gym103371H Or Machine 最短路

Problem – H – Codeforces

题意:你有一个长为$n$的数组$\{x_i\}$,元素都在$[0, 2^8)$范围内。

你还有一个长为$l$的操作序列,每次操作会有两个数$a,b$,表示$x[a] = x[a] \text{or} x[b]$(按位或)。

现在给定一个数$t$,要求你在操作序列中循环执行操作(如果已经执行完了$l$个则下一次操作从第一个重新开始),总共执行$t$个操作之后,输出得到的序列。

$n,l \le 2^{18} = 262144$,$t \le 10^{18}$。


显然每一位是独立的,所以转换成$8$次只有0和1的问题即可。

继续阅读“GP of Korea Gym103371H Or Machine 最短路”

HDU6987 Cycle Binary 反演,杜教筛

Cycle Binary – HDU 6987 – Virtual Judge (vjudge.net)

题意:对一个01串$s$,设$s$的权值是最大的$k$,使得$s$的某个前缀可以表示成一个相同的串重复$k$次,并且剩余的部分一定是循环节的一个前缀。

现在给定$n$,对所有长为$n$的01串,求其权值的和。

继续阅读“HDU6987 Cycle Binary 反演,杜教筛”

2021多校10 Game of Death 容斥原理,FFT

题意:

有$n$个哈皮要打枪,每个人会独立随机选择一个其他人瞄准,然后所有人同时开枪。

每个人只开一枪,并且有$p$的概率打中(每个人是否打中是独立的)。

问最后剩$0$~$n$个人存活的概率,对$998244353$取模。


如果没有“不能瞄准自己”的限制的话就很简单了,但是这里有这个限制。

我们可以考虑容斥原理,选择一个集合$S$,限制$S$中的人都没有死,但是其他人不管死活。假设这个概率是$g(S)$,显然所有集合大小相等的$S$的答案都是相同的,不妨设$|S| = i$时答案是$g_i$,可以得到

$$ g_i = \left(\frac {i – 1} {n – 1} (1 – p) + \frac {n – i} {n – 1}\right) ^ i \left(\frac i {n – 1} (1 – p) + \frac {n – i – 1} {n – 1}\right) ^ {n – i} $$

出奇的简单,只需要分是否在$S$中讨论就行了。因为其他人死活不考虑,所以只需要使$S$中所有人没被打到。

继续阅读“2021多校10 Game of Death 容斥原理,FFT”

Gym101128I Text Processor 后缀自动机,LCT

题意:给定一个字符串,每次询问一个它的一个子串中有多少个本质不同的子串。注意询问的子串长度是固定的。

鉴于本题的特殊性可以用后缀数组+set维护。但是对于一般情况(询问区间有包含),用set维护前驱后继的做法就不太好搞了。

区间本质不同子串统计有一个经典做法是后缀自动机+LCT+线段树维护。

继续阅读“Gym101128I Text Processor 后缀自动机,LCT”