RainAir
My OI Blog
RainAir

题解
文章归档

「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 去围观

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 去围观

「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 去围观

密码保护:CF 题解汇集

这篇文章受密码保护,输入密码才能看哦

   320   2019-07-13 去围观

ZROI466小 G 的数

最近从某个地方看到了这个题。。。所以回来补一下题解。 题目描述 题解 直接求期望不太好求,我们可以考虑求出每一种条件下的概率,最后乘上直径长度就可以了。 我们设 $f_{i,j,k}$ 表示在以 $i$ 为根的子树里,目前不跨过 $i$ 节点的最长链是 $j$,子树的直径是…

   139   2019-07-08 去围观

「NOI2005」瑰丽华尔兹

题目链接 题目大意 现在有一个 $n\times m$ 的矩阵,给定的起始点上有个钢琴,矩阵上有些方格是障碍物,用连续的区间 $[l,r]$ 和一个参数 $d$ 表示在时间 $[l,r]$ 时会向 $d$ 方向滑动(上下左右),当然每个时间点可以选择让钢琴不动,不允许钢琴超出边界或者碰到障…

   96   2019-07-07 去围观

HDU 3480 Division

题目链接 题意 有长度为 n 的序列,定义一个集合的代价是$(MAX-MIN)^2$,要求你找出 m 个集合,在满足下面图片的限制的情况下,使得总代价最小。 多组数据,每组数据 $n \leq 10^4,m \leq 5 \times 10^3$,保证答案在 int 范围内。 题解 观察题目 发现让你选取 M …

   95   2019-07-06 去围观

TCO2017 Round 1A PolygonRotation

题目描述 We have a convex polygon in the XY plane. The vertices of the polygon are the points (x[0], y[0]), (x[1], y[1]), ... in clockwise order. You are given the vector s x and y. In order to make the implementation simpler the polygon and its r…

   210   2019-06-09 去围观
加载更多
标签
近期评论