题目链接
题意；求$\sum_{i=1}^n i^kr^i$模$1e9 + 7$。($n, r \le 10^{18}$，$k \le 2000$)。

这题几个星期前看了一下午题解没看懂，现在看了一会就看懂了。可能是我太蠢了。

技不如人，甘拜下风。

题目链接

题意：有一个$n \times m$的01矩阵，第$i$行的数之和为$A_i$，第$j$列的数之和为$B_j$，已知数组$B$的所有元素，求有多少种可能的数组$A$。模$10^9 + 7$。($1 \le n, m \le 50$)

爆搜过十万(误)。

斜率优化什么的太难写了啊。。。。

一道自己出的小菜题。

做不来小学数学题了。

我没有脑子。

我错了。

自闭了。

五边形数$p_i$定义为：$\frac{i(3i - 1)}{2}$。

一个定理：$\prod_{i=1}^{\infty} (1 - x^i) = \sum_{i=-\infty}^{\infty} (-1)^i x^{p_i}$。

证明自行看维基。

题目链接

题意：你有一个随机数生成器，有$\frac{1}{2}$的概率返回$0$，$\frac{1}{2}$的概率返回$1$。你要用它来构造一个新的随机数生成器，这个新的随机数生成器生成的数是$[1, n]$内的整数，且生成$i$的概率为$\frac{a_i}{a_1 + a_2 + \dots + a_n}$。求在调用一次新随机数生成器的过程中最少期望调用多少次原随机数生成器。$1 \leqslant n \leqslant 10^6$，$1 \leqslant \sum_{i=1}^n a_i \leqslant 10^7$。

题目链接

题意：给你一个数组，求它有多少个子区间所有数都出现了奇数次。$n \leqslant 2 \times 10^5$。

首先给每一个数$\text{rand}$一个权值，那么一个区间满足条件等价于这个区间所有数的权值异或和$\text{xor}$上这个区间去重后的所有数的权值异或和为$0$。

题目链接

设$a_1 < a_2 < a_3 < a_4$，$S = a_1 + a_2 + a_3 + a_4$，则$\frac{S}{2} < a_2 + a_4 < a_3 + a_4 < S$。所以$a_2 + a_4$和$a_3 + a_4$不整除$S$。那么第一问的答案$\leqslant 4$，通过观察样例，我们发现第一问的答案$= 4$。

NOIP2018爆零记。

Miller Rabin

Miller Rabin 是一个快速判断质数的方法。

$a^{x-1} \equiv 1 \pmod x(1 \leqslant a \leqslant x - 1)$这个等式，在$x$是质数的时候根据费马小定理是成立的。在$x$不是质数的时候，这个等式有大概率不成立。

qwq..

一些定义

$ \Big \lbrace { n \atop k } \Big \rbrace $为第二类斯特林数，即把将一个有$n$件物品的集合划分为$k$个非空子集的方法数。

我好菜啊!

A

由于每个方格可以翻转或旋转，所以我们如果可以不考虑重合构造出一条无限长的链，就可以通过翻转来使它没有重合的问题(比如强制这条链的方向是向左上)。

感觉自己数据结构水平越来越菜了。。。

题目链接

这个东西我想不出什么靠谱的做法，但是发现如果没有修改，用kd树很容易乱搞。在每个节点上维护框住所有点的矩形，如果查询的直线和这个矩形有交就往下做(这个kd树甚至都不能按坐标划分，但它跑得飞快)

test

test

test

test

test