RainAir
My OI Blog
RainAir

RainAir’s Blog

  NOIP 2019 Bless All!!!!

「BZOJ1129」Per

题意:给你一个序列s,你把这个序列的所有不同排列按字典序排列后,求s的排名mod m 不保证 $m$ 是质数。 题解:我们记 $cnt_i$ 表示填到当前 $i$ 这个数还有多少个,不难发现题目要求的是: $$\sum_{i=1}^n \frac{(n-i)!}{\Pi_j cnt_j} (\sum_{j < s_i}cnt_j)$$ 显…

   79   2019-08-18 去围观

「CF1097G」Vladislav and a Great Legend

CF1097G 题意大概是给 $n$ 个点的树,定义 $f(S)$ 表示 $S$ 中所有的点构成的斯坦纳树的大小。求 $$\sum_{S \subseteq [1,2,\cdots,n],S \neq \emptyset} f(S)^k$$ 解:首先看到 $k$ 次方和发现不太好求,我们可以拆成斯特林数的形式: $$x^k = \sum_{i=0}^k i! (^x_i…

   133   2019-08-03 去围观

「CF1106F」Lunar New Year and a Recursive Sequence

题目链接 首先 $f_{[1\cdots k-1]} = 1$,所以发现每个 $f_x$ 都可以表示成 $f_k^e$ 的形式。 我们首先通过矩阵乘法算出来 $f_k^e = f_n$ 的解,然后就是解方程 $$f_k^e \equiv m (\mod 998244353)$$ 了。 这是一个简单的离散对数入门题,我们就两边取个 $log_g$ $$(lo…

   136   2019-08-01 去围观

最小割模型

网络流题目中,如果一种物品有两种状态(选或不选),告诉你每一种状态产生的收益/代价,我们就可以通过使用最小割模型来解决这个问题。但是如果物品的状态扩展到了 $k$ 种,我们就需要用一种新的建图方法。 我们拿两道题目举例: RatingProgressAward *TCO2017 Semi…

   108   2019-08-01 去围观

概率期望入门

排版彻底崩了不管了 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)$ 常用公式 $$\sum_{i=0}^n…

   190   2019-07-29 去围观

ZROI Contest 350

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

   119   2019-07-26 去围观

「BZOJ2142」 礼物/exLucas

题目链接 题目是让你求一堆 $1e9$ 范围的组合数并且模数不保证是质数。 对于这一类题目,我们有一种叫做 exlucas 的方法来算组合数(但是和 lucas 没有半毛钱关系)。 首先我们将模数 $m$ 质因数分解,最后用 CRT 合并一下就好了。 然后我们现在只需要考虑组合数对 $p^…

   145   2019-07-21 去围观

「ZROI851」exexBSBSGSGS

题意:求$a^x \equiv b(\mod p^e)$ 的最小整数解。 $3 < p \leq 50,p^e \leq 10^18,a\nmid p,b \nmid p$,询问不超过 $1000$ 组。 暴力分跑 bsgs 其实就可以了...因为保证了 $(a,p^e) = 1$。 但是这样显然会 T,于是我们就不要往 bsgs 的方面去想了。 我们考虑 $p$…

   188   2019-07-21 去围观

简单数论公式

记录各种我这种数论菜鸡不会的式子。。。可能有很 zz 的式子大佬不要嘲笑 整除与不定方程 $d|a,d|b \Leftrightarrow d|(a-b)$ 证明:$a = pd,b = qd,a-b = (p-q)d$ 2. $(a,b)|d \Leftrightarrow ax+by = d$ 存在整数解。 证明: 从右往左推:令 $g=(a,b)$,则有 $…

   131   2019-07-18 去围观

「ZROI849」 大厦

题目描述:给你若干条形如 $x+y=c$ 或 $x-y=c$ 的直线,这些直线与坐标轴的夹角是 45 度,问在矩形 $(0,0) \to (W,H)$ 中,有多少个子矩形。 图片示意: 上图有 $19$ 个子矩形。 $n \leq 10^5$ 首先这一题目 $O(n^3)$ 的复杂度十分好做:就是枚举三条边 去 map 找一下…

   141   2019-07-17 去围观
加载更多
标签
近期评论