Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「SDOI2013」随机数生成器 - 数学 + BSGS

    给定 p p a a b b x1 x_1 ,现有一数列

    求最小的 i i 满足 xi=t x_i = t

    于  BSGS, BZOJ, SDOI, 数学, 数论 继续阅读

  2. 线性基学习笔记

    线性基是竞赛中常用来解决子集异或一类题目的算法。

    于  学习笔记, 数学, 算法模板, 线性基 继续阅读

  3. 计算几何学习笔记

    计算几何(Computational Geometry),是一系列使用计算机解决几何问题的算法。与解析几何相比,计算几何更适合计算机运算,精度较高,运算速度较快,并且易于编写。

    本文只包含二维计算几何在 OI 中的部分应用。

    于  学习笔记, 数学, 算法模板, 计算几何 继续阅读

  4. 「HAOI2007」反素数 - 搜索

    对于任何正整数 x x ,其约数的个数记作 g(x) g(x) ,例如 g(1)=1 g(1) = 1 g(6)=4 g(6) = 4 。如果某个正整数 x x 对于任何 i(0,x) i \in (0, x) 都满足 g(x)>g(i) g(x) > g(i) ,则称 x x 为反质数。

    给定一个数 N N ,求最大的不超过 N N 的反质数。

    于  BZOJ, HAOI, 搜索, 数学 继续阅读

  5. 「NOIP2016」组合数问题 - 递推 + 前缀和

    组合数表示的是从 n n 个物品中选出 m m 个物品的方案数。举个例子,从 (1,2,3) (1, 2, 3) 三个物品中选择两个物品可以有 (1,2) (1, 2) (1,3) (1, 3) (2,3) (2, 3) 这三种选择方法。

    根据组合数的定义,我们可以给出计算组合数的一般公式:

    Cnm=n!m!(nm)! C_n ^ m = \frac{n!}{m!(n - m)!}

    其中 n!=1×2××n n! = 1 \times 2 \times \cdots \times n

    小葱想知道如果给定 n n m m k k ,对于所有的 0in 0 \leq i \leq n 0jmin(i,m) 0 \leq j \leq \min(i, m) 有多少对 (i,j) (i, j) 满足是 k k 的倍数。

    于  NOIP, 前缀和, 数学, 组合数 继续阅读

  6. 「HAOI2008」糖果传递 - 数学

    n n 个小朋友坐成一圈,每人有 ai a_i 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 1 1 。求使所有人获得均等糖果的最小代价。

    于  BZOJ, HAOI, 数学 继续阅读

  7. 「HAOI2008」硬币购物 - 背包 DP + 容斥原理

    一共有 4 4 种硬币。面值分别为 c1,c2,c3,c4 c_1, c_2, c_3, c_4 。某人去商店买东西,去了 n n 次。每次带 di d_i ci c_i 硬币,买 si s_i 的价格的东西。请问每次有多少种付款方法?

    于  BZOJ, DP, HAOI, 容斥原理, 数学, 背包 DP 继续阅读

  8. 「HAOI2008」圆上的整点 - 数学

    求一个给定的圆 x2+y2=r2 x ^ 2 + y ^ 2 = r ^ 2 ,在圆周上有多少个点的坐标是整数。

    于  BZOJ, HAOI, 数学 继续阅读

  9. 「SCOI2009」游戏 - 群论 + 背包 DP

    windy 学会了一种游戏。对于 1 1 N N N N 个数字,都有唯一且不同的 1 1 N N 的数字与之对应。最开始 windy 把数字按顺序 1,2,3,,N 1, 2, 3, \ldots, N 写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为 1,2,3,,N 1, 2, 3, \ldots, N

    如:1,2,3,4,5,6 1, 2, 3, 4, 5, 6 对应的关系为

    {122331455466 \begin{cases} 1 \rightarrow 2 \\ 2 \rightarrow 3 \\ 3 \rightarrow 1 \\ 4 \rightarrow 5 \\ 5 \rightarrow 4 \\ 6 \rightarrow 6 \end{cases}

    windy 的操作如下:

    这时,我们就有若干排 1 1 N N 的排列,上例中有 7 7 排。现在 windy 想知道,对于所有可能的对应关系,有多少种可能的排数。

    于  BZOJ, DP, SCOI, 数学, 群论, 背包 DP 继续阅读

  10. 「NOIP2014」解方程 - Hash

    已知多项式方程:

    a0+a1x+a2x2++anxn=0 a_0 + a_1 x + a_2 x ^ 2 + \cdots + a_n x ^ n = 0

    求这个方程在 [1,m] [1, m] 内的整数解。

    于  BZOJ, CodeVS, Hash, NOIP, 数学 继续阅读