「ZROJ」造数据

比赛已经开始了,可是鸽王小W还没有造好数据。

他现在在赶造数据。数据是一个 $n\times m \ (1\le n, m\le 1000)$ 的矩阵 $a_{i, j}$,现在小Y对这个矩阵很感兴趣。小Y想知道,如果定义函数
$$
f(x_l,x_r,y_l,y_r)=\sum_{i=x_l}^{x_r} \sum_{j=y_l}^{y_r} a_{i,j}
$$
那么对于给定的 $X_l, X_r, Y_l, Y_r$ ,问
$$
\sum_{1 \le a \le b \le n, X_l \le b-a+1 \le X_r} \ \ \ \ \ \sum_{1 \le c \le d \le m, Y_l \le d-c+1 \le Y_r} f(a, b, c, d)
$$
即询问包含行的个数在 $X_l$ 到 $X_r$ 之间,包含列的个数在 $Y_l$ 到 $Y_r$ 之间的所有子矩阵的元素和的和。

小Y一共会给出 $q$ 组询问,他想让你帮他快速回答这些询问。由于答案可能很大,小Y只要你输出答案对 $998244353$ 取模之后的结果。

「NOIp2015」信息传递

有 $n$ 个同学(编号为 $1$ 到 $n$ )正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 $i$ 的同学的信息传递对象是编号为 $T_i$ 的同学。

游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息, 但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自 己的生日时,游戏结束。请问该游戏一共可以进行几轮?

DP做题记录

因为自己的dp太弱,于是有了这篇文章 $\mathcal{Q\omega Q}$ 。都是一些 我不会的 NOIp的题目。

生成函数(1)-基本法则及运算

下面的一些文章会逐步介绍生成函数(边学边写)。

区间操作模板

暑假的时候终于会了线段树(的板子)啦,也懒得再写一份笔记了,毕竟 oi-wiki 上说的也超级详细。

「BZOJ1257」余数之和

给定$\ n, k\ $,计算$\ \sum_{i = 1} ^{n}k \bmod i\ $。

树状数组

最近,学习了树状数组这种十分常用的数据结构,真是有趣呢。

树状数组可以在常数很小的 $O(n\log n)$ 复杂度内实现单点加法以及区间求和(区间加也行?)。

「BZOJ3884」上帝与集合的正确用法-扩展欧拉定理

这道题要求的是$\ 2^{2^{2^{\cdots}}}\bmod p$。

「SDOI2010」古代猪文-CRT+Lucas定理

这道题要让我们求的是$\ G^{\sum_{d|m}C^d_n} \bmod 999911659\ $。

Miller-Rabin素性检测

我们常用的单个素数检测复杂度为$\ O(\sqrt{n})\ $,当$\ n \ $很大时,这种方法就不适用了,于是我们就有了$\mathrm{Miller-Rabin}$素数判定方法,这种判定的复杂度可以降至$\ O(k\log ^3 n)$(其中$\ k \ $时测试的轮数)

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×