排列组合
加法/乘法原理
加法原理是分类，乘法原理讲究分步
加法原理
有一个问题，它有 \(n\) 类解决办法，对于第 \(a\) 类解决办法，有 \(x_a\) 种方法完成 那么，总解决方法数就是: $x_1+x_2+x_3+\cdots+x_{n-1}+x_n$乘法原理
有一个问题，它有 \(n\) 个步骤，对于第 \(a\) 个步骤，有 \(x_a\) 种方法完成 那么，总解决方法数就是: $x_1*x_2*x_3*\cdots*x_{n-1}*x_n$ 这两个规律是显而易见的，甚至被放到了小学奥数里…排列组合
先亮公式 排列: $$A_n^m={{n!} \over {(n-m)!}}$$ 组合: $$C_n^m={{n!} \over {m!(n-m)!}}$$ P.S.: 组合一作 \(P_n^m\) 这是一种较老的表示方法，本博客中使用 \(c_n^m\) 特别定义: $0!=1$ 我相信你的内心一定是迷茫的，让我们来看看这两个东西定义与使用
排列
定义: 从 \(n\) 个数中任意取出 \(m\) 个数，求有多少种方法，不同顺序算作另一种那么这种问题第一下就会想到乘法原理 对于第一位数， 有 \(n\) 种选法，对于第 2 位数， 有 \(n-1\) 种选法，对于第3位数， 有 \(n-3\) 种选法，对于第 \(y\) 位数， 有 \(n-(y-1)\) 种选法 根据乘法原理得$A_n^m=n*(n-1)*(n-2)*(n-3)*\cdots*(n-m)$ 即$A_n^m={{n!} \over {(n-m)!}}$
组合
定义: 从 \(n\) 个数中任意取出 \(m\) 个数，求有多少种方法，不同顺序算同一种这个的区别在于不同的顺序在于同一组，不过这么相似，显然是通过上面的推得 也就是说我们要将 $A_n^m$ 中去重，那么我们就要考虑，从 \(m\) 个数中取出的长度为\(m\)的序列会有多少组不同的组合，由排列得 $A_m^m=m!$ $\therefore C_n^m={{n!} \over {m!(n-m)!}}$
组合的特别性质
第一个: $$C_n^m=C_n^(n-m)$$ 证明:$$\because C_n^{n-m}={n! \over {(n-m)![n-(n-m)]!}}={n! \over {(n-m)!n!}}$$ $$\because {C_n^m=n! \over {m!(n-m)!}}$$ $$\therefore {C_n^m=C_n^{n-m}}$$ 第二个: $$ C_n^m=C_{n-1}^m+C_{n-1}^{m-1} $$ 证明:$$ C_{n-1}^m+C_{n-1}^{m-1}={{(n-1)! \over {m!(n-m-1)!}} + {(n-1)! \over {(m-1)!(n-m)!}}} $$ $$={(n-1)(n-2)(n-3) \cdots m \over (n-m)!}+{(n-1)(n-2)(n-3) \cdots (m+1) \over (n-m-1)!}$$ $$={(n-1)(n-2)(n-3) \cdots (m+1)(n-m+m) \over (n-m)!}$$ $$={n! \over {m!(n-m)!}}$$ 这个实际上就是杨辉三角啦 第三个: $$C_n^0+C_n^1+C_n^2+\cdots+C_n^{n-1}+C_n^n=2^n$$ 这个的证明，再用等式的性质…..你们的博主还没有这么厉害… 实际上就是说，你想象一下对 \(n\) 个物品中随意取(1,n)个，这不就相当于你在你在 \(n\) 个物品中间，随意取几个吗 有点眼熟啊…这不是01背包思想吗!! 把每个物品当作一个 0/1 数值，选为 1 不选为 0 ，你么根据乘法原理，总共有 \(2\^n\) 种可能P2282 组合数问题
题目链接:[https://www.luogu.org/problemnew/show/P2822]题目第一眼过去想让人暴力套公式计算,但是…\(t<10^4+1\) 这个速度就比较温暖人心了,有没有什么快速解决的办法的呢? 当然有!杨辉三角了解一下 当然我们不能每个数组数据都处理一波,\(n<2000+1\),后面前缀和保留每一行,后面遍历行数前缀相加就可以了 千万不要忘记边做边取模
代码
#include <cstdio>
using namespace std;
long long t,k;
long long n,m;
long long c[2200][2200];
// n m
long long cnt=0;
long long sum[2200][2200];
inline long long min(long long a,long long b){return a<b?a:b;}
int main(){
scanf("%lld%lld",&t,&k);
for(int i=0;i<=2100;i++){//预处理
if(i==0){
for(int j=0;j<=i;j++){
c[0][j]=1;
if(c[0][j]%k==0) sum[0][j]=1;// 前缀和
else sum[0][j]=0;
}
}
else for(int j=0;j<=i;j++){
if(j==0||j==i) c[i][j]=1;
else c[i][j]=(c[i-1][j-1]+c[i-1][j])%k; // 记得取模
if(j==0){
if(c[i][j]%k==0) sum[i][j]=1;
else sum[i][j]=0;
}
else {
if(c[i][j]%k==0) sum[i][j]=sum[i][j-1]+1;
else sum[i][j]=sum[i][j-1];
}
}
}
for(int i=1;i<=t;i++){//及其稀少的主部分
cnt=0;// 别忘记设0
scanf("%lld%lld",&n,&m);
for(long long j=0;j<=n;j++){
cnt+=sum[j][min(m,j)];
}
printf("%lld\n",cnt);
}
}
long long呢,因为乘的时候可能会出事
“数论基础 – 排列组合 – Luogu P2822 组合数问题”上的1条回复
[…] 排列组合 […]