ResurrectionTX

分类

比赛(7) 笔记(6) 题解(32)

/ 注册

全部文章（共7篇）

2020牛客NOIP赛前集训营-提高组（第六场）A 袜子分配

这种期望题一般要不就是对每个点单独计算贡献要不就是算形如的东西。那么这题是对每个点单独算贡献。一共有2n只袜子，所以就有2n！种拿法。将每对袜子拆成两个不一样的，那么他们在一起当且仅当在n个组的同一组内即为种，因为拆成了两个不一样的，所以要乘2。然后每个袜子对期望的贡献是独立的，所以剩下...

概率期望数论组合数学

2020-10-29

5 660

2020牛客NOIP赛前集训营-提高组（第四场）

要是早点写这题就能赛时调过了，就能Rank2了(痛哭看到题目先来化一波式子：为了简化式子，令，，发现长得都很像，所以其实只要求出形如的东西就行了。考虑每个位置的权值对这个式子上面的指数的贡献，我们可以得知这个式子就等于。组合意义是每个位置选或者不选的所有情况，最后再减...

线段树数论

2020-10-25

13 836

UOJ #62.【UR #5】怎样跑得更快

Description 传送门 Solution 如题，有 \[\sum_{j = 1} ^ n gcd(i, j) ^ c \times lcm(i, j) ^ d \times x_j \equiv b_i \pmod p \] 首先先把\(lcm(i, j)\)用\(\f...

数论莫比乌斯反演 UOJ

2020-06-12

0 369

组合数学

懒得复制的一些东西 1.1 可重复组合 \(n\)个数中选择\(r\)个数，每个数可以重复选择多次。方案数为\(\binom{n + r - 1}{r}\)。考虑若没有选择多次的条件，就是在\(n\)个数中选择一个子数列，满足\(a_i < a_{i + 1}\)，现在有了可以重复...

组合数学数论

2020-06-12

0 454

斐波那契数

\(1.1.1\)斐波那契循环节 \[gcd(fib_n, fib_m) = fib_{gcd(n, m)} \] 考虑设\(n < m\)，\(fib_n = a\)，\(fib_{n + 1} = b\)，那么对应的有\(fib_{n + 2} = a + b\)，\(fib_...

数论

2020-06-12

0 329

Luogu P4707 【重返现世】

Description 传送门 Solution 对于每种原料，如果我们能求出它们的期望出现时间，那么第\(k\)小的期望出现时间就是答案。因为在第\(k\)小的原料被收集之前，比它更早出现的原料已经被收集过了，第\(k\)小的原料就是第\(k\)个被收集到的原料。第\(k\)小的原料...

min-max反演数论 Luogu

2020-06-12

0 432

Luogu P5856 【「SWTR-03」Game】

Description 传送门 Solution 读完题面之后我们首先可以想到要进行质因数分解。因为每次只能除以\(prime^z\)也就是说每次我们只能消除某一个质因子多出来的部分，所以对于每个质因子可以分开考虑。消去某个质因子多出来的部分只需要把这个质因子所有出现过的在每个数中...

状压DP 数论 Luogu

2020-06-12

0 420