数论&组合数学常见结论及例题

数论&组合数学常见结论及例题

球盒模型（八种）

参考链接。给定 个小球 个盒子。

  • 球同，盒不同、不能空

隔板法： 个小球即一共 个空，分成 堆即 个隔板，答案为 。

  • 球同，盒不同、能空

隔板法：多出 个虚空球，答案为 。

  • 球同，盒同、能空

的 项的系数。动态规划，答案为

$$dp[i][j]=
\left{\right.$$

1
2
3
4
5
6
7
8
9
10
int dp[15][15];
void choose(int n) {
    for(int i = 0; i < n; i ++) {
        for(int j = 1; j < n; j ++) {
            if(i <= 1 || j == 1) dp[i][j] = 1;
            else if (i < j) dp[i][j] = dp[i][j - 1];
            else dp[i][j] = dp[i][j - 1] + dp[i - j][j];
        }
    }
}
  • 球同，盒同、不能空

的 项的系数。动态规划，答案为

$$dp[n][m]=
\left{\right.$$

  • 球不同，盒同、不能空

第二类斯特林数 ，答案为

$$dp[n][m]=
\left{且\right.$$

  • 球不同，盒同、能空

第二类斯特林数之和 ，答案为 。

  • 球不同，盒不同、不能空

第二类斯特林数乘上 的阶乘 ，答案为 。

  • 球不同，盒不同、能空

答案为 。

麦乐鸡定理

给定两个互质的数 ，定义 $x=an+bm（a \ge 0,b \ge 0），当x > n*m-n-m$ 时，该式子恒成立。

抽屉原理（鸽巢原理）

将 个物体，划分为 组，那么有至少一组有两个（或以上）的物体。

哥德巴赫猜想

任何一个大于 的整数都可写成三个质数之和；任何一个大于 的偶数都可写成两个素数之和。

除法、取模运算的本质

有公式： ， 。

与、或、异或

运算 运算符、数学符号表示 解释
与 &、and 同1出1
或 |、or 有1出1
异或 ^、、xor 不同出1

一些结论：

对于给定的 和序列 ，有：Misplaced &\pmb {X=(X &a_1)or(X&a_2)or…or(X&a_n)} 。
原理是 意味着取交集， 意味着取子集。来源 - 牛客小白月赛49C

调和级数近似公式

1
log(n) + 0.5772156649 + 1.0 / (2 * n)

欧拉函数常见性质

  • 中与 互质的数之和为 。
  • 若 ， 互质，则 。实际上，所有满足这一条件的函数统称为积性函数。
  • 若 是积性函数，且有 ，那么 。
  • 若 为质数，且满足 ，
    • ，那么 。
    • ，那么 。
  • 。

    如 ，则 ，那么 。

  • （欧拉反演）。

组合数学常见性质

  • $k C^k_n=nC^{k-1}_{n-1}$ ；
  • $C_k^nC_m^k=C_m^nC_{m-n}^{m-k}$ ；
  • ；
  • ；
  • 。
  • 二项式反演：$\left{\right. $ ；
  • ；
  • ；
  • ；
  • ；
  • 拉格朗日恒等式： 。

lucas定理

Lucas 定理内容如下：对于质数 ，有

观察上述表达式，可知 和 一定是小于 的数，可以直接求解， 可以继续用 Lucas 定理求解。这也就要求 的范围不能够太大，一般在 左右。边界条件：当 的时候，返回 。

时间复杂度为 ，其中 为预处理组合数的复杂度， 为单次求组合数的复杂度。

1
2
3
4
long long Lucas(long long n, long lm, long long p) {
  if (m == 0) return 1;
  return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}
1
2
3
4
def Lucas(n, m, p):
    if m == 0:
        return 1
    return (C(n % p, m % p, p) * Lucas(n // p, m // p, p)) % p

范德蒙德卷积公式

在数量为 的堆中选 个元素，和分别在数量为 、 的堆中选 、 个元素的方案数是相同的，即 ；

变体：

  • ；
  • 。
推论 1 及证明

推论 2 及证明

推论 3 及证明

推论 4 及证明

其中 是我们较为熟悉的网格图路径计数的方案数。所以我们可以考虑其组合意义的证明。

在一张网格图中，从 走到 共走 步。规定 位于网格图左上角，其中向下走了 步，向右走了 步，方案数为 。

换个视角，我们将 步拆成两部分走，先走 步，再走 步，那么 步中若有 步向右，则 步中就有 步向右，故得证。

卡特兰数

是一类奇特的组合数，前几项为 。如遇到以下问题，则直接套用即可。

  • 【括号匹配问题】 个左括号和 个右括号组成的合法括号序列的数量，为 。
  • 【进出栈问题】 经过一个栈，形成的合法出栈序列的数量，为 。
  • 【二叉树生成问题】 个节点构成的不同二叉树的数量，为 。
  • 【路径数量问题】在平面直角坐标系上，每一步只能向上或向右走，从 走到 ，并且除两个端点外不接触直线 的路线数量，为 。

计算公式： ， 。

狄利克雷卷积

， 。

斐波那契数列

通项公式： 。

直接结论：

  • 卡西尼性质： ；
  • ；
  • （由上一条写两遍相减得到）；
  • 若存在序列 则 ；
  • 齐肯多夫定理：任何正整数都可以表示成若干个不连续的斐波那契数（ 开始）可以用贪心实现。

求和公式结论：

  • 奇数项求和： ；
  • 偶数项求和： ；
  • 平方和： ；
  • ；
  • ；
  • 。

数论结论：

  • ；
  • ；
  • 当 为 型素数时， ；
  • 当 为 型素数时， ；
  • 的周期 （ 时取到等号）；
  • 既是斐波那契数又是平方数的有且仅有 。

杂

  • 负数取模得到的是负数，如果要用 判断的话请取绝对值；

  • 辗转相除法原式为 ，推广到 项为 ，

    • 该推论在“四则运算后 ”这类题中有特殊意义，如求解 时See；

  • 以下式子成立： 。求解上式满足条件的 的数量即为求比 小且与其互质的数的个数，即用欧拉函数求解 。

  • 已知序列 ，定义集合 ，现在要求解 ，即为求解 ，换句话说，即为求解后缀 。

  • 连续四个数互质的情况如下，当 为奇数时， 一定互质；而当 为偶数时，$\left{互质时互质时\right.$ See；

  • 由 可以推广得到 ，由此可以得到一个 的答案周期See；

  • 对于长度为 的数列 ，将其任意均分为两个长度为 的数列 ，随后对 非递减排序、对 非递增排序，定义 ，那么答案为 数列前 大的数之和减去前 小的数之和See。

  • 令 $\left{\right.$ ，如果该式子有解，那么存在前提条件 $\left{同奇偶\right.；进一步，此时最小的a的取值为\dfrac{X-Y}{2}$ See。

    然而，上方方程并不总是有解的，只有当变量增加到三个时，才一定有解，即：在保证上方前提条件成立的情况下，求解 $\left{\right.，则一定存在一组解{\dfrac{X-Y}{2},\dfrac{X-Y}{2},Y}$ See。

  • 已知序列 是由序列 、序列 、……、序列 合并而成，且合并过程中各序列内元素相对顺序不变，记 是 序列的最大前缀和，则 See 。

  • Misplaced &x+y=x|y+x&y ，对于两个数字 和 ，如果将 变为 ，同时将 变为 Misplaced &x&y ，那么在本质上即将 二进制模式下的全部 移动到了 的对应的位置上 See 。

  • 一个正整数 异或、加上另一个正整数 后奇偶性不发生变化： See 。

常见例题

题意：将 至 的每个数字分组，使得每一组的数字之和均为质数。输出每一个数字所在的组别，且要求分出的组数最少 See 。

考察哥德巴赫猜想，记全部数字之和为 ，分类讨论如下：

  • 为 质数时，只需要分入同一组；
  • 当 为偶数时，由猜想可知一定能分成两个质数，可以证明其中较小的那个一定小于 ，暴力枚举分组；
  • 当 为质数时，特殊判断出答案；
  • 其余情况一定能被分成三组，其中 单独成组， 后成为偶数，重复讨论二的过程即可。

题意：给定一个长度为 的数组，定义这个数组是 的，当且仅当可以把数组分成两个子序列，这两个子序列的元素之和相等。现在你需要删除最少的元素，使得删除后的数组不是 的。

最少删除一个元素——如果原数组存在奇数，则直接删除这个奇数即可；反之，我们发现，对数列同除以一个数不影响计算，故我们只需要找到最大的满足 成立的 ，随后将全部的 变为 ，此时一定有一个奇数（换句话说，我们可以对原数列的每一个元素不断的除以 直到出现奇数为止），删除这个奇数即可 See 。

题意：设当前有一个数字为 ，减去、加上最少的数字使得其能被 整除。

最少减去 这个很好想；最少加上 也比较好想，但是更简便的方法为加上 ，这个式子等价于前面这一坨。

题意：给定一个整数 ，用恰好 个 的幂次数之和表示它。例如： ，答案为 。

结论1： 合法当且仅当 __builtin_popcountll(n) <= k && k <= n ，显然。

结论2： ，所以我们可以将二进制位看作是数组，然后从高位向低位推，一个高位等于两个低位，直到数组之和恰好等于 ，随后依次输出即可。举例说明， ，即答案为 个 、 个 、……。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
signed main() {
    int n, k;
    cin >> n >> k;
    
    int cnt = __builtin_popcountll(n);
    
    if (k < cnt || n < k) {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    
    vector<int> num;
    while (n) {
        num.push_back(n % 2);
        n /= 2;
    }
    
    for (int i = num.size() - 1; i > 0; i--) {
        int p = min(k - cnt, num[i]);
        num[i] -= p;
        num[i - 1] += 2 * p;
        cnt += p;
    }
    
    for (int i = 0; i < num.size(); i++) {
        for (int j = 1; j <= num[i]; j++) {
            cout << (1LL << i) << " ";
        }
    }
}

题意： 个取值在 之间的数之和为 的方案数

答案为 See1 See2。

1
2
3
4
5
6
 Z clac(int n, int k, int m) {
    Z ans = 0; 
        ans += C(n, i) * C(m - i * k + n - 1, n - 1) * pow(-1, i);
    }
    return ans;
}

先考虑没有 的限制，那么即球盒模型： 个球放入 个盒子，球同、盒子不同、能空。使用隔板法得到公式：C(m + n - 1, n - 1) ； 下面加上取值范围后进一步考虑：假设现在 个数之和为 ，运用上述隔板法可得公式：C(m - k + n - 1, n - 1) ； 随后，选择任意一个数字，将其加上 ，这样，这个数字一定不满足条件，选法为：C(n, 1) ； 此时，至少有一个数字是不满足条件的，按照一般流程，到这里，C(m + n - 1, n - 1) - C(n, 1) * C(m - k + n - 1, n - 1) 即是答案；但是，这样的操作会导致重复的部分，所以这里要使用容斥原理将重复部分去除（关于为什么会重复，试比较概率论中的加法公式）。

/END/