Menci

眉眼如初,岁月如故

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


  1. 「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, 前缀和, 数学, 组合数 继续阅读

  2. 「SDOI2016」排列计数 - 组合数学 + 错位排列

    求有多少种长度为 n n 的序列 A A ,满足以下条件:

    • 1 1 ~ n n n n 个数在序列中各出现了一次
    • 若第 i i 个数 A[i] A[i] 的值为 i i ,则称 i i 是稳定的。序列恰好有 m m 个数是稳定的

    满足条件的序列可能很多,序列数对 109+7 10 ^ 9 + 7 取模。

    于  BZOJ, COGS, SDOI, 数学, 组合数, 组合数学, 错位排列 继续阅读

  3. 「BZOJ 4403」序列统计 - 组合数

    给定三个正整数 N N L L R R ,统计长度在 1 1 N N 之间,元素大小都在 L L R R 之间的单调不降序列的数量。输出答案对 106+3 10 ^ 6 + 3 取模的结果。

    于  BZOJ, Lucas 定理, 乘法逆元, 数学, 数论, 组合数, 组合数学 继续阅读

  4. 「UVa 10253」Series-Parallel Networks - 整数划分 + 组合数

    串并联网络有两个端点,一个是源,一个是汇,递归定义如下:

    1. 一条单独的边是串并联网络;
    2. G1 G1 G2 G2 是串并联网络,则将它们的源和汇分别接在一起也能得到串并联网络(并联);
    3. G1 G1 G2 G2 是串并联网络,则将 G1 G1 的源和 G2 G2 的汇接在一起也能得到串并联网络(串联);

    并联或串联在一起的各个部分可以调换顺序,顺序改变后的串并联网络和之前是相同的。求 N N 条边能组成多少种不同的串并联网络。

    于  UVa, 回溯, 数学, 整数划分, 组合数, 计数原理, 递推 继续阅读

  5. 「POJ 1737」Connected Graph - 组合数 + 计数原理 + 递推

    给定 N N N50 N \leq 50 )个点,在平面上固定其位置,求这些点最多能组成多少个不同的无向连通图。

    于  POJ, 数学, 组合数, 计数原理, 递推, 高精度 继续阅读