NOI2021 加油！

RainAir's Blog

「CF1106F」Lunar New Year and a Recursive Sequence

题目链接 首先 $f_{[1\cdots k-1]} = 1$，所以发现每个 $f_x$ 都可以表示成 $f_k^e$ 的形式。 我们首先通过矩阵乘法算出来 $f_k^e = f_n$ 的解，然后就是解方程 然后因为 $g = 3$，用 BSGS 算出两项，最后用 exgcd 解出 $e$ 直接代入即可。 代码:/* * Author: RainAir * Time: 2019-07-...

  • RainAir
  • August 1, 2019
  • 1 comments

    • 最小割模型

    网络流题目中，如果一种物品有两种状态（选或不选），告诉你每一种状态产生的收益/代价，我们就可以通过使用最小割模型来解决这个问题。但是如果物品的状态扩展到了 $k$ 种，我们就需要用一种新的建图方法。 我们拿两道题目举例：RatingProgressAward*TCO2017 Semifinal 题目链接 如果对于积分做了前缀和之后我们发现题目就是要求在满足限制的条件下最大化区间和。 对于一个...

  • RainAir
  • August 1, 2019
  • 1 comments

    • 概率期望入门

    排版彻底崩了不管了 QAQ基础概念随机变量：有多种可能的取值的变量。$P(A)$：事件 $A$ 发生的概率。$E(X)$：随机变量 X 的期望值，$E(X) = \sum_{x} P(x=i)*i$独立事件：互相不影响的事件，满足 $P(AB) = P(A)P(B),E(AB) = E(A)E(B)$常用公式

  • RainAir
  • July 29, 2019
  • No comments

    • ZROI Contest 350

    B现在有一棵树 要求对于每个点 $x$ ,求所有点到他的链的最大点权之和 $n \leq 4 \times 10^5$题解：又是我不会的思博题。 这种题目我们可以首先考虑在链上的做法： 显然有一种基于分治的方法，但是很难扩展到树上。 所以我们考虑如果变成边权是不是好维护。。（ 我们考虑定义点 $i$ 和 $i+1$ 之间的边的边权是 $max\{a_{i},a_{i+1}\}...

  • RainAir
  • July 26, 2019
  • No comments

    • 「BZOJ2142」 礼物/exLucas

    题目链接 题目是让你求一堆 $1e9$ 范围的组合数并且模数不保证是质数。 对于这一类题目，我们有一种叫做 exlucas 的方法来算组合数（但是和 lucas 没有半毛钱关系）。 首先我们将模数 $m$ 质因数分解，最后用 CRT 合并一下就好了。 然后我们现在只需要考虑组合数对 $p^e$ 取模的情况了。 这样还是不能直接去乘逆元的，因为分母可能有因子 $p$，直接求逆元会变成 $0$ ...

  • RainAir
  • July 21, 2019
  • 2 comments