$ABC\ 132F$$Description$给出 $n, k$ ,求由正整数组成的长度为 $k$ 的序列的个数,并使任意两个相邻元素的乘积最多为 $<= n$ ,答案对 $10 ^ 9 + 7$ 取模。 $Solution$首先很容易看出与除法分块相关。 $yy$ 一下发现第二层答案就是 ...
[JXOI2018]排序问题
$[JXOI2018]$ 排序问题$Description$ $Solution$先解释一下题意。 就是给你一个长度为 $n$ 的序列,然后允许插入 $m$ 个数到这个序列中,这 $m$ 个数的取值范围在 $[l,\ r]$ 之间,然后把这个序列排序,然后生成一个关于 $x_i$ 的编号排列,求使这 ...
XOR Partitioning
$XOR\ Partitioning$$Description$给一个序列,问有多少种方法能够把这个序列分成若干块使得每一块的异或和都相同。答案对 $1e9+7$ 取模。 $Solution$观察本题,可以发现几个性质: 对于两段异或和 $1 - i,\ 1 - j$ ,规定 $i < j$ ...
51nod B君的游戏
$B$ 君的游戏$Description$ $Solution$打表好题*2 这道题使我对博弈论打表的理解加深了一些。 首先我们考虑对于一个数所造成的影响,只与他在二进制下 $1$ 的个数有关。 所以状态总数只有 $64$ 种。 我们根据上一题)的经验,可以知道本题的转移就是枚举一个数的所有子集并 ...
51nod 小C的游戏
小 $C$ 的游戏$Description$ $Solution$打表好题 首先约定 $P-position$ 表示先手必败, $N-position$ 表示先手必胜。 本题并不需要用到 $SG$ 函数等知识,只需要懂得如何对博弈论的局面进行转移即可。 如此就引出了关于博弈论题目的打表技巧。 首先, ...
51nod B君的竞技场
$B$ 君的竞技场$Description$ $Solution$设 $f_{i, j}$ 表示胜场到 $i$ 场,败场 $j$ 场的概率。$$f_{i, j} = f_{i - 1, j} \times p + f_{i, j - 1} \times (1 - p)$$然后难点就在于输赢的概率怎么 ...