嘤傻傻

关于组合数学(●'◡'●)

今天是来绍兴一中的第三天,模拟赛Day2,超难的。晚上吃薯片,发现根本吃不完,我就不该买大包,(¬︿ ̿¬☆)

公式

组合数学包括了两大部分,一块是排列,一块是组合。排列是在一个集合中取出的有序子集,组合是无序子集。对于公式这个东西我还是经常会分不清楚,但说不定用多了就会了呢 XD(因为不会打正常的公式,所以下面的公式都会比较。。。丑)
1.排列公式: A(k,n)=n!/((n-k)!)
【表示是在n个数中取出k个元素,相同的数但是排列顺序不同也算是不同的情况呢】
特别的,如果是全排列的话就直接等于 n!
在这里有个很棒的函数,可以字典序输出全排列: next_permutation ,意思是全排列中字典序排在下一个的排序,并会直接在序列上更新。另外,若不存在排名更靠后的排列会返回flase,否则会返回true。同理也有 prev_permutation 。这两个函数的头文件是 < algorithm >

2.组合公式: C(k,n)=n!/(k!(n-m)!)
【表示是在n个数中取出k个元素,只考虑数,不考虑排列】
特别的,C(0,n)=1

3.组合数递推公式: C(k,n)=C(k-1,n-1)+C(k,n-1)

4.卢卡斯定理: 对于 C(k,n) mod p 来说,我们可以令 k=sp+q ,n=tp+r ( q,r<=p ) ,然后可以得到 C(k,n) mod p 与 C(s,t)C(q,r) mod p 同余,并且 C(k,n) % p = C(m % p,n % p)C(m/p,n/p) 【根据onglu所说,这两个式子是一样的,但是我看不出来,也证不出来,所以我决定把两个都背下来!( •̀ ω •́ )y】

算法

暴力组合数

1
2
3
4
5
6
7
8
9
int C(int n,int k)
{
int ans=1;
for(int i=n;i>n-k;i--)
ans*=i;
for(int i=1;i<=k;i++)
ans/=i;
return ans;
}

杨辉三角求组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void init()
{
sj[0][0]=1;
for(int i=1;i<=2004;i++)
{
sj[i][0]=1;
for(int j=1;j<=i;j++)
sj[i][j]=(sj[i-1][j]+sj[i-1][j-1])%mod;
}
}
int C(int m,int k)
{
return sj[m][k];
}

线性组合数

这个技能还需要会线性求逆元。。。有点难啊,今天模拟赛就用到了,但是那时的我还不会呢。。。(好像现在也不会的样子??)
总之先背下来再说辣,看上去特别厉害的样子嘞

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int fac[100010],inv[100010],n=100005;
void init()
{
inv[0]=inv[1]=fac[0]=1;
for(int i=2;i<=n;i++)
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<=n;i++)
inv[i]=1ll*inv[i-1]*inv[i]%mod;
for(int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
}
int C(int n,int m)
{
return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}

这里附上我模拟赛的题目,还有我好不容易才AC的代码(眼泪汪汪)
膜法
【题目描述】 【题目描述】
M 王国 正在举行盛大的开仪式!为了庆祝,准备聘请王国中德高望重的膜法师来表演炫酷的膜法
膜法师的施咒语都存在他书籍中,一共有 n 本膜法书,第 i 本膜法书上有着 i 条咒语,这些咒语都互不相同。
膜法师为这次的准备了m 个环节,第 i 个环节,膜法师会从 li 到 ri 的膜法书中某一本选出若干个咒语来组成表演的膜法的一个片段。具体,膜师如果决定这环节咒语在第 j 本书中选取,那么他会选 ki + j − l 条咒语。
膜法师的多种多样,两种膜法不同,当且仅存在至少一个环节,膜法师选择的书不同,或者在同一本魔法书上选取的咒语不一样。现在国王想知道,膜法师一共可能表演出多少种不同的膜法。
【输入格式】
第一行两个正整数 表示 n, m 。
接下来 m 行,每行三个正整数,分别表示 li, ri, ki。
【输出格式】
输出一个数,表示不同膜法的种注意种类数可能很多只需输出再模 1e9 + 7 的方案数即可。
【样例输入】
3 2
1 2 1
2 3 1
【样例输出】
10
【数据范围】
对于 30 % 的数据,n, m ≤ 2000。
对于 60 % 的数据,n ≤ 2000, m ≤ 105。
对于 100 % 的数据,n, m ≤ 105, ki ≤ li ≤ ri ≤ n。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>

using namespace std;
const int mod=1000000000+7;
int read()
{
char c;int num,f=1;
while(c=getchar(),c<'0' || c>'9') if(c=='-') f=-1;num=c-'0';
while(c=getchar(),c>='0' && c<='0') num=num*10+c-'0';
return f*num;
}
int n,m,sum[100010],ans=1;
struct node
{
int k,l,r;
}qaq[100010];
int po(int x)
{
int num=1;
for(int i=2;i<=x;i++)
num*=i;
return num;
}

int main()
{
freopen("m.in","r",stdin);
freopen("m.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=m;i++)
{
qaq[i].l=read();qaq[i].r=read();qaq[i].k=read();
for(int j=1;j<i;j++)
{
if(qaq[j].l==qaq[i].l)
{
if(qaq[j].r<=qaq[i].r)
qaq[j].l=0;
else
qaq[i].l=0;
}
}
}
for(int i=1;i<=m;i++)
{
if(qaq[i].l==0)
continue;
for(int j=qaq[i].l;j<=qaq[i].r;j++)
{
int a=qaq[i].k+j-qaq[i].l;
sum[i]+=po(j)/(po(a)*po(j-a));
}
ans*=sum[i];
ans%=mod;
}
cout<<ans<<endl;
return 0;
}

emmm,好像还有一些没有提及的算法呢。。。算了,好疲惫的,下次再写好了,(●’◡’●),就先这样辣。

总结

这篇博客是看到onglu大佬的博客之后写的,根据他的博客写了一些自己的见解。当然也要感谢他晚上的口嫌体正直,在我只吃了几片薯片的情况下,把我的薯片吃完了,这样牺牲自己也努力不让我发胖的人真的太少见了,感动到哭泣。。(不,其实是生气,但是打不过他的泪水,😭)