计数组合【2024蓝桥杯0基础】-学习笔记

文章目录

• 计数原理
• • 排列数
  • 组合数
  • • 组合数性质
    • 例题分析
    • • 代码复现
    • 例题2
    • • 状态分析
      • 代码复现
  • 常见的排列组合问题
  • 圆排列
  • • • 代码复现
  • 第二类斯特林数
• 感悟

计数原理

排列数

组合数

组合数性质

例题分析

代码复现

def ksm(a, b, c):
    ans = 1%c
    while b != 0:
        if b % 2 == 0:
            ans = ans * a %c
        a = a * a % c
        b  //= 2
    return ans
#利用费马小定理求逆元
def inv(a):
    return ksm(a, mod- 2, mod)

#求组合数
def C(n, m):
    p, q = 1, 1
    for i in range(1, m+1):
        p = p * (n + 1 -i) % mod
        q = q * i % mod
    return p * inv(q) % mod
mod = 1000000007
n, a, b = map(int, input().split())
ans = ksm(2, n, mod)-1-C(n, a) - C(n, b)
ans = ((ans%mod) + mod) % mod#这里是防止对负数取模

例题2

状态分析

这题就是单纯的数学分析的题目了

代码复现

常见的排列组合问题

圆排列

###例题分析

代码复现

import os
import sys

# 请在此输入您的代码
n, k = map(int, input().split())
#n个不同的球放到k个相同的箱子里面，不允许空
#dp[i][j]表示i个球放入j个箱子里的方案书
#1.第i个球开辟一个箱子：dp[i-1][j-1]
#2.已经有了j个箱子：dp[i-1][j]*j
mod = 1000000007
dp = [[0]*(k+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,min(k, i)+1):
        #j == 1 表示所有的球放到一个箱子&j == i因为非空表示每个箱子只放一个球
        if j == 1 or j == i:
            dp[i][j] = 1
        else:
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * j)%mod
print(dp[n][k])

第二类斯特林数

搜集了一些资料觉得这个博客讲的很详细：第二类斯特林数
内容截图如下：

感悟

复习了一下高中的知识觉得很微妙，继续加油！
蓝桥杯云课学习笔记分享，欢迎大佬们批评指正！

一直在进步就好咯！

by 闻不多