数学

数学

排列组合

• 不可重复组合：C(n,m)
• 可重复组合：C(n+m-1,m)
• 不可重复排列：P(n,m)
• 可重复排列：m的n次方

二项式定理

容斥原理

整数分拆

性质

• 整数n拆分成最大数为m的拆分数，和整数n拆分成m个数的和的拆分数相等。
• 整数n拆分成最多不超过m个数的和的拆分数，和整数n拆分成最大不超过m的拆分数相等。
• 整数n拆分成互不相同的若干奇数的和的拆分数,和整数n拆分成自共轭的Ferrers图像的拆分数相等。

最大m分拆数

记将整数n拆分成最大不超过m的拆分数为

def integer_partition(n, m):
    if n == 0:
        return 1
    if m == 0:
        return 0
    m = min(m, n)
    dp = [0] * (n + 1)
    dp[0] = 1
    for j in range(1, m + 1):
        for i in range(j, n + 1):
            dp[i] += dp[i - j]  # f(i,j)=f(i,j-1)+f(i-j,j)
    return dp[n]

模意义下的逆元

• 模的逆元：
• 除法取模：
• 当且仅当a和p互质时，a在模p意义下的乘法逆元存在。
• 利用扩展欧里几得算法或费马小定理求解逆元。

  费马小定理：如果p是一个质数，而整数a不是p的倍数，则有。

矩阵运算

• 矩阵快速幂

高斯消元

拓展

• 生成函数
• 莫比乌斯反演
• 快速傅里叶变换