组合数学（一）QAQ

[TOC]

组合

$C_n^r=C_{n-1}^r+C_{n-1}^{r-1}$ 对于第n个元素，不取时，相当于前n-1个元素中取r个，取时，是前n-1个元素中取r-1个。

像个杨辉三角：

C(0,0)

C(1,0) C(1,1)

C(2,0) C(2,1) C(2,2)

C(3,0) C(3,1) C(3,2) C(3,3)

….. ….. …..

如果要求解C(n,r)，可以先求解出C(n-1,r) 和 C(n-1,r-1)；再运用公式相加即可。很明显，这是一个与Fib数列类似的递归计算。只不过求Fib(n)时，只有一个参数，而这里有二个参数而已。（还是直接求把。。还有用dp的方法）

Cayley公式

一个完全图K_n有$n^{n-2}$棵生成树，即n个有标号1~n的顶点的树的个数为：$n^{n-2}$

证明：你画个图

给定一棵带标号的无根树，找出编号最小的叶子节点，写下与它相邻的节点的编号，然后删掉这个叶子节点。反复执行这个操作直到只剩两个节点为止。由于节点数n>2的树总存在叶子节点，因此一棵n个节点的无根树唯一地对应了一个长度为n-2的数列，数列中的每个数都在1到n的范围内。

简化为：n个数字可重复的排列到n-2个位置上去。

不全相异的排列

n个元素组成的多重集，$a_i$重复$n_i$次，$n=∑_{i=1}^kn_i$,从n个元素中选取r个排列，求不同的排列数。

若r=n ,为：$\frac{n!}{n_1!n_2!…n_k!}$

重复排列和重复组合

排列：在n个不同物体中可重复选取r个排列：$n^r$

组合：…… 组合：$C_{n+r-1}^r$

证明组合：对于1~n的x集合中选取r个元素，然后对应的构造r个y集合中的元素，对应关系为：$y_i=x_i+i-1$，

故……

圆周排列

a、b、c、d，普通排列：24，圆周排列：6 = 24/4 也就说；普通数量/个数 = （n-1）！

生成全排列

序数法

任何 $m=a_{n-1}(n-1)!+a_{n-2}(n-2)!+a_{n-3}(n-3)!+……+a_2·2!+a_1·1!$ ①

其中a1 = m%2， a2=(m/2)%3 , a3=(m/2/3)%4 ……直到m/……=0；

那么！a集合（$a_{n-1}~a_1$）共有n！种排列对不对！那么怎样把1,2，……n的一个排列和①联系起来呢？

某一个n阶排列的序号是m，那么将m转换为阶乘进制数后，阶乘进制数的第i位就是在i右面比i小的元素个数。例如4阶排列中（从0开始计数的）第19个排列的序号是19，将19转换成阶乘进制数是3010，那么，第一位是0，表明1的右面没有比1小的元素，而第二位是1，则2的右面有一个元素小于2，第三位是0，即3的右面没有比它小的元素，第四位是3，4的右面有3个元素小于它。显然，这个排列是4 2 1 3。

字典序法

很简单就是1234 、 1243、 1324、 1342、……这样的全排列生成顺序

方法是：eg：上一个排列数为：3421 (p.s.以下的i j k都是下标) 1~n

  1. 求$ i = max ( j|a_j-1<a_j ) = 2$
  2. 求$ j = max(k|a_i-1<a_k)= 2$
  3. 交换$a_i-1$ 和 $a_j$ ，得：4321
  4. 将$a_ia_{i+1}a_{i+2}……a_n$逆序：得4123。

Poj 1833 可以使用stl中的next_permutation(op1,op2)自动生成字典序的下一个全排列。

op1是放排列的数组首地址a，op2是排列的长度a+n。

到最后一个排列时返回为false。

但是这一题卡输出，用stl的中的

1
2
copy(a,a+n-1,ostream_iterator<int>(cout," "));
cout<<a[n-1]<<endl;

参考用法：

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
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <iterator>
using namespace std;
int n;
int main()
{
    int a[1300];
    int m,k;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<k;i++)
            next_permutation(a,a+n);
        for(int i=0;i<n;i++)
            printf("%d ",a[i]);
        copy(a,a+n-1,ostream_iterator<int>(cout," "));
        cout<<a[n-1]<<endl;
    }
    return 0;
}

邻位互换法

计蒜客构造题 [bellring]

仔细想想不就是把n插入到已完成的n-1阶排列的不同位置中得到n阶排列吗？

n=1; 1

n=2; 12 , 21

n=3; 123, 132, 312, 321, 231, 213

……

用这种方法可以产生出任意n阶全排列，（而且符合bellring中的移动规律，即每个数移动的位置最多为1，就能一下子构造出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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/**
	本算法的思想也是希望以（12…n）作为n个元素1，2，…，n的第一个排列，
	然后按照某种方法，由一个排列（p）＝（p1p2…pn）直接生成下一个排列，
	直到全部排列生成完毕为止。

	以n＝4为例，开始在排列1234的各数上方加一个左箭头“←”，
	当一个数上方箭头所指的一侧，相邻的数比该数小时，便称该数处于活动状态。
	从排列（p）＝（p1p2…pn）生成下一个排列的算法如下：
	（1）若排列（p）＝（p1p2…pn）中无一数处于活动状态，则停止，否则转（2）；
	（2）求所有处于活动状态的数中的最大者，设为k，
		k和它的箭头所指的一侧的相邻数互换位置，转（3）；
	（3）令比k大的所有数的箭头改变方向，转（1）。
*/
#include <bits/stdc++.h>


using namespace std;


enum DIR{LEFT=-1,RIGHT=1};


/*	函数功能：判断下标i所指p中元素是否处于活动状态
 *	输入参数：p	in,指向n个字符的一个当前排列
 *			dir	in,标记p中每个元素的箭头方向
 *			i	in,待判定元素的下标
 *			N	in,待排列字符的个数
 *	返回值：	true 表示待判定元素为活动状态，
 *			false 表示待判定元素处于非活动状态
 */
bool IsActive(const char *p,const DIR *dir,const int i,const int N)
{
	if(i+dir[i] < 0 || i+dir[i] >= N)
		return false;
	if(p[i+dir[i]] < p[i])	//箭头所指一侧相邻的数比该数小
		return true;
	else return false;
}


/*	函数功能：找到p中处于活动状态的数中的最大者
 *	输入参数：p	in,指向n个字符的一个当前排列
 *			dir in,标记p中每个元素的箭头方向
 *			N	in,待排列字符的个数
 *	返回值：上述最大者的下标，-1表示调用参数有误,N表示没有活动者
 */
int MaxActive(const char *p,const DIR *dir,const int N)
{
	int k=N;
	for(int i=0;i<N;i++)
		if(IsActive(p,dir,i,N) && (p[i] > p[k]))
			k = i;
	return k;
}


/*	函数功能：交换下标i所指元素与其箭头方向所指元素,原位交换
 *	输入参数：p	inout,指向n个字符的一个当前排列
 *			dir inout,标记p中每个元素的箭头方向
 *			i	in,待交换元素的下标
 *	返回值：	true 表示交换成功
 *			false 表示交换失败，失败原因为调用参数有误。
 */
bool Swap(char *p, DIR *dir, int *i)
{
	if(p == NULL || dir == NULL)
		return false;


	//交换相邻的元素；
	char temp = p[*i];
	p[*i] = p[*i+dir[*i]];
	p[*i+dir[*i]] = temp;


	//元素相关的箭头也得交换
	DIR T = dir[*i];
	dir[*i] = dir[*i+T];
	dir[*i+T] = T;


	*i = *i + T;	//使*i依旧是未交换前*i所指元素的下标
	return true;
}


/*	函数功能：上述算法思路第三步，修改所以比k大的元素的箭头方向，原位修改
 *	输入参数：p	in,指向n个字符的一个当前排列
 *			dir	inout,标记p中每个元素的箭头方向
 *			k	in,p中处于活动状态的最大者的下标，由MaxActive函数求出
 *			N	in,缓冲区p的长度,也是待排列字符的个数
 *	返回值：	true 表示函数执行成功
 *			false 表示函数执行失败，失败原因为调用参数有误
 */
bool ModifyDir(const char *p,DIR *dir,const int k,const int N)
{
	if(p == NULL || dir == NULL)
		return false;
	for(int i=0;i<N;i++)
		if(p[i]>p[k])
			dir[i] = (dir[i] == LEFT ? RIGHT : LEFT);
	return true;
}
int main()
{
	int N =0;
	cin>>N;
	char *p = new char [N+1];
	DIR *dir = new DIR [N];
	for(int i=0;i<N;i++)
	{
		p[i] = '1'+i;
		dir[i] = LEFT;
	}
	p[N]='\0';
	int k=0;
	for(int i=0;i<strlen(p)-1;i++)
            printf("%d ",p[i]-'0');
        printf("%d\n",p[strlen(p)-1]-'0');
	int c = 1;
	do
	{
		k = MaxActive(p,dir,N);
		if(k == N)
			break;
		Swap(p,dir,&k);
		ModifyDir(p,dir,k,N);
		for(int i=0;i<strlen(p)-1;i++)
            printf("%d ",p[i]-'0');
        printf("%d\n",p[strlen(p)-1]-'0');

	} while (1);
	delete []p;
	delete []dir;
	return 0;
}

卡特兰数

$$
a_{n}=\frac{4n-2}{n+1}a_{n-1}
$$

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … …

该递推关系的解是：
$$
a_{n}=\frac{C_{2n}^{n}}{n+1} (n=1,2,3,…)
$$
eg. 出栈的种数与卡特兰数：

① 对于出栈序列中的每一个数字，在它后面的、比它小的所有数字，一定是按递减顺序排列的。

② 给定一个入栈顺序：1 2 3 …. n，一共有多少种合法的出栈顺序？

答案是 卡特兰数。即一共有：$h(n)=\frac{C_{2n}^{n}}{n+1} $ 种合法的出栈顺序。

如果仅仅只需要求出一共有多少种合法的出栈顺序，其实就是求出组合 C(2n,n)就可以了。

组合数模板

n,m大，MOD小

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
#define ll long long  
const int N=1000100;  
const int MOD=99991;  
ll f[N];  
ll Fp(ll a,ll n)  
{  
    ll ans=1;  
    while(n)  
    {  
        if(n&1) ans=(ans*a)%MOD;  
        a=a*a%MOD;  
        n>>=1;  
    }  
    return ans;  
}  
ll Lucas(ll a,ll k)  
{  
    ll ans=1;  
    while(a&&k)  
    {  
        ll a1=a%MOD;  
        ll b1=k%MOD;  
        if(a1<b1) return 0;  
        ans=ans*f[a1]*Fp(f[b1]*f[a1-b1]%MOD,MOD-2)%MOD;  
        a/=MOD;  
        k/=MOD;  
    }  
    return ans;  
}  
void Init()  
{  
    f[0]=1;  
    for(int i=1;i<=MOD;i++)  
    {  
        f[i]=f[i-1]*i%MOD;  
    }  
}  
int main()  
{  
    Init();  
    printf("%I64d\n",Lucas(5,2));  
}

n，m小，mod大

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
#define ll long long  
const int MOD=1e9+7;  
const int N=1000100;  
ll f[N];  
ll Fp(ll a,ll n)  
{  
    ll ans=1;  
    while(n)  
    {  
        if(n&1) ans=ans*a%MOD;  
        a=a*a%MOD;  
        n>>=1;  
    }  
    return ans;  
}  
ll C(int n,int m)  
{  
    if(n<m) return 0;  
    return f[n]*Fp(f[m],MOD-2)%MOD*Fp(f[n-m],MOD-2)%MOD;  
}  
void Init()  
{  
    f[0]=1;  
    for(int i=1;i<N;i++) f[i]=f[i-1]*i%MOD;  
}  
int main()  
{  
    Init();  
    printf("%I64d\n",C(5,2));  
}

n，m很小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define ll long long 
const int MOD=1000000007;  
const int N=20;  
ll C[N][N];  
int main()  
{  
    C[0][0]=C[1][0]=C[1][1]=1;  
    for(int i=2;i<N;i++)  
    {  
        C[i][0]=1;  
        for(int j=1;j<N;j++)  
        {  
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;  
        }  
    }  
}

母函数

定义：对于序列$a_0,a_1,a_2 … $构造一个函数：

$$
G(x)=a_0+a_1x+a_2x^2+…
$$

则，函数G(x)就是序列$a_0,a_1,a_2…$的母函数。

比如说一个普通型母函数的应用：

有质量为1,2,3的砝码各一枚：

（1）可以称出多少种不同的质量？

解：1个1g砝码可以用1+x表示，1表示不用，x表示用1g砝码

​ 1个2g砝码可用$1+x^2$表示……

​ 1个3g砝码$1+x^3$……

​ 则其母函数$G(x)=(1+x)(1+x^2)(1+x^3)=1+x+x^2+2x^3+x^4+x^5+x^6$

​ x上的指数表示质量，x前的系数表示搭配种类。

​ 故可以称出6种。

（2）若砝码有无穷个？

解：以2g砝码为例，那么2g砝码可以组成：$(1+x^2+x^4+x^6……)$

因此：$G(x)=(1+x+x^2+x^3+……)(1+x^2+x^4+x^6+……)(1+x^3+x^6+x^9+……)$

模板：

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
//这个比较快速
/**
K对应具体问题中物品的种类数。
v[i]表示该乘积表达式第i个因子的权重，对应于具体问题的每个物品的价值或者权重。
n1[i]表示该乘积表达式第i个因子的起始系数，对应于具体问题中的每个物品的最少个数，即最少要取多少个。
n2[i]表示该乘积表达式第i个因子的终止系数，对应于具体问题中的每个物品的最多个数，即最多要取多少个。
对于表达式(1+x+x^2)(x^8+x^10)(x^5+x^10+x^15+x^20)，v[3]={1,2,5}，n1[3]={0,4,1}，n2[3]={2,5,4}。
解题的关键是要确定v、n1、n2数组的值。
通常n1都为0，但有时候不是这样。
n2有时候是无限大。
P是可能的最大指数。
如果n2为无穷大，那么第二层循环条件j<=n2[i]可以去掉。
a[i],i为指数，内容为系数。
*/
//初始化a，因为有last，所以这里无需初始化其他位

a[0]=1;
int last=0;
for (int i=0;i<K;i++)
{
	int last2=min(last+n2[i]*v[i],P);//计算下一次的last
	memset(b,0,sizeof(int)*(last2+1));//只清空b[0..last2]
	for (int j=n1[i];j<=n2[i]&&j*v[i]<=last2;j++)//这里是last2
		for (int k=0;k<=last&&k+j*v[i]<=last2;k++)//这里一个是last，一个是last2
			b[k+j*v[i]]+=a[k];
	memcpy(a,b,sizeof(int)*(last2+1));//b赋值给a，只赋值0..last2
	last=last2;//更新last
}

例题：HDU2082

示例代码:

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
#include <bits/stdc++.h>
using namespace std;
int v[100],n[100],a[100],b[100],last,last2,sum;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0; i<26; i++)
        {
            scanf("%d",&n[i]);
            v[i]=i+1;
        }
        a[0]=1;last=0;
        //初始化a，因为有last，所以这里无需初始化其他位
        for (int i=0; i<26; i++)
        {
            int last2=min(last+n[i]*v[i],50);//计算下一次的last
            memset(b,0,sizeof(int)*(last2+1));//只清空b[0..last2]
            for (int j=0; j<=n[i]&&j*v[i]<=last2; j++) //这里是last2
                for (int k=0; k<=last&&k+j*v[i]<=last2; k++) //这里一个是last，一个是last2
                    b[k+j*v[i]]+=a[k];
            memcpy(a,b,sizeof(int)*(last2+1));//b赋值给a，只赋值0..last2
            last=last2;//更新last
        }
        int ans=0;
        for(int i=1; i<=50; i++)
            if(a[i])   ans+=a[i];
        printf("%d\n",ans);
    }
    return 0;
}

整数拆分

//大整数分解模板

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
typedef long long ll;
map<ll, int>m;
const int mod = 10000019;
const int times = 50;//测试50次
ll mul(ll a, ll b, ll m)
//求a*b%m
{
    ll ans = 0;
    a %= m;
    while(b)
    {
        if(b & 1)ans = (ans + a) % m;
        b /= 2;
        a = (a + a) % m;
    }
    return ans;
}
ll pow(ll a, ll b, ll m)
//a^b % m
{
    ll ans = 1;
    a %= m;
    while(b)
    {
        if(b & 1)ans = mul(a, ans, m);
        b /= 2;
        a = mul(a, a, m);
    }
    ans %= m;
    return ans;
}
bool Miller_Rabin(ll n, int repeat)//n是测试的大数，repeat是测试重复次数
{
    if(n == 2 || n == 3)return true;//特判
    if(n % 2 == 0 || n == 1)return false;//偶数和1

    //将n-1分解成2^s*d
    ll d = n - 1;
    int s = 0;
    while(!(d & 1)) ++s, d >>= 1;
    //srand((unsigned)time(NULL));在最开始调用即可
    for(int i = 0; i < repeat; i++)//重复repeat次
    {
        ll a = rand() % (n - 3) + 2;//取一个随机数,[2,n-1)
        ll x = pow(a, d, n);
        ll y = 0;
        for(int j = 0; j < s; j++)
        {
            y = mul(x, x, n);
            if(y == 1 && x != 1 && x != (n - 1))return false;
            x = y;
        }
        if(y != 1)return false;//费马小定理
    }
    return true;
}
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
ll pollard_rho(ll n, ll c)//找到n的一个因子
{
    ll x = rand() % (n - 2) + 1;
    ll y = x, i = 1, k = 2;
    while(1)
    {
        i++;
        x = (mul(x, x, n) + c) + n;//不断调整x2
        ll d = gcd(y - x, n);
        if(1 < d && d < n)
            return d;//找到因子
        if(y == x)
            return n;//找到循环，返回n，重新来
        if(i == k)//一个优化
        {
            y = x;
            k <<= 1;
        }
    }
}
void Find(ll n, ll c)
{
    if(n == 1)return;//递归出口

    if(Miller_Rabin(n, times))//如果是素数，就加入
    {
        //factor[index++]=n;
        m[n]++;
        return;
    }

    ll p = n;
    while(p >= n)
        p = pollard_rho(p, c--);//不断找因子，知道找到为止，返回n说明没找到

    Find(p, c);
    Find(n / p, c);
}
int main()
{
    ll n;srand((unsigned)time(NULL));
    while(cin >> n)
    {
        m.clear();
        Find(n, rand() % (n - 1) + 1);//这是自己设置的一个数
        cout<<n<<" = ";
        for(map<ll ,int>::iterator it = m.begin(); it != m.end();)
        {it->first<<" ^ "<<it->second;
            if((++it) != m.end())
               cout<<" * ";
            cout<<
        }
        cout<<endl;
    }
    return 0;
}

Ferrrs图像

一个自上而下的n层各自组成的图像，$m_i$为第i层的格子数。当$m_i≥m{i+1}$，即上层的格子数不少于下层的格子数时，称之为Ferrers图像。

绕$y=-x$旋转得到的图像仍然是Ferrers图像，这样两个称为一对共轭Ferrers图像。

整数的拆分也可以用这个图像来表示。

可根据图像证明定理：整数n拆分成k个数的和的拆分数，与数n拆分成最大数为k的拆分数相等。

eg：24=5+5+5+4+3+2 的图像 共轭图像的话，24=6+6+5+4+3，

可以看出，24拆分成6个数的最大数=24拆分成最大数为6的拆分数

……

指数型母函数

在不全相异的排列那一p里面，r=n可以容易求出，但是当r一般情况的时候就复杂了。

对于给定的数列$a_0,a_1,a_2,…,a_n,…，$通常称为形式幂级数，即：
$$
Σ_{n=0}^∞\frac{a_n}{n!}x^n=a_0+a_1x+\frac{a_2}{2!}x^2+\frac{a_3}{3!}x^3+…+\frac{a_n}{n!}x^n+…
$$
为数列$a_0,a_1,a_2,…,a_n,…$的指数型母函数，这里规定0！=1。

这样，对于一个多重集，其中$a_i$重复了$n_i$次，$n=∑_{i=1}^nn_i$，从n个元素中取r个元素排列，不同的排列数对应的指数型母函数：
$$
G(x)=(1+\frac{x}{1!}+\frac{x^2}{2!}+…+\frac{x^{n_1}}{n_1!})(1+\frac{x}{1!}+\frac{x^2}{2!}+…+\frac{x^{n_2}}{n_2!})+…+(1+\frac{x}{1!}+\frac{x^2}{2!}+…+\frac{x^{n_k}}{n_k!})
$$
例题：有1,2,3,4,个数字组成的五位数中，要求数1出现次数不超过2次，但不能不出现；2不超过1次；3最多3次，可以不出现；4出现次数为偶数。求满足上述条件的数的个数。

解：$C_r$对应的指数型母函数为
$$
G(x)=(\frac{x}{1!}+\frac{x^2}{2!})(1+\frac{x}{1!})(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!})(1+\frac{x^2}{2!}+\frac{x^4}{4!})
$$
解得x上指数为5的系数为215。

p.s.4的偶数次之所以到$x^4$是因为再多也不满足条件啊。

HDU排列组合 题

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long LL;
using namespace std;
const int N = 11;
double c1[N],c2[N];     //注意类型
LL fac[N];
 
void cal()
{
    fac[0]=1;           //0!会被用到
    for(int i=1;i<N;i++)
        fac[i]=i*fac[i-1];
}
 
int main()
{
    cal();
    int n,r;
    while(~scanf("%d%d",&n,&r))
    {
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
 
        c1[0]=1;
        int num;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num);
            if(num==0) continue;
            for(int j=0;j<=r;j++)
            {
                for(int k=0;k<=num&&k+j<=r;k++)
                {
                    c2[k+j]+=c1[j]/fac[k];
                }
            }
            for(int j=0;j<=r;j++)
            {
                c1[j]=c2[j];
                c2[j]=0;
            }
        }

        printf("%.0lf\n",c1[r]*fac[r]);
    }
 
	return 0;
}

递推关系

斐波那契

斯特林数 Stiring

###第一类斯特林数

有正负，其绝对值是包含n个元素的集合分作k个环排列的方法数目

递推公式：

​ S（n，0）= 0

​ S（1，1） = 1

​ S（n+1，k）= S（n，k-1) + nS（n，k）

第三个式子是这样的，n+1个元素分成k个环，可以理解为前n个元素分成k-1个环，第n+1个自成一个环的种类数量，加上前n个元素分成k个环，第n+1个元素插入到第i个元素左边。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//第一类Stirling数s(p,k)计数的是把p个对象排成k个非空循环排列的方法数
#define ll long long
const int N=1000;
const int MOD=1e9+7;
ll s[N][N];//存放要求的Stirling数
void Init()
{
    s[1][1]=1;
    for(int i=2;i<N;i++)
    {
        for(int j=1;j<=i;j++)
        {
            s[i][j]=(s[i-1][j-1]+(i-1)*s[i-1][j])%MOD;
        }
    }
}

第二类斯特林数

将包含n个元素的集合划分为正好k个非空子集方法的数目

递推公式：

​ S（n，k）= 0（n<k ||k==0）

​ S（n，n） = S（n，1） = 1

​ S（n，k）= S（n-1，k-1) + kS（n-1，k）

第三个式子是这样的，n个元素分成k集合，可以理解为前n-1个元素分成k-1个集合，第n个自成一个集合的种类数量，加上前n-1个元素分成k个环，第n个元素在k个集合中选择放到里面去。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
第二类Stirling数S(p,k)计数的是把p元素集合划分到k个不可区分的盒子里且没有空盒子的划分个数。
*/
#define ll long long
const int N=1000;
const int MOD=1e9+7;
ll s[N][N];//存放要求的Stirling数
void Init()
{
    s[1][1]=1;
    for(int i=2;i<N;i++)
    {
        for(int j=1;j<=i;j++)
        {
            s[i][j]=(s[i-1][j-1]+j*s[i-1][j])%MOD;
        }
    }
}

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

小可爱的小可爱，<br/>拖肥的娘亲，<br/>划水的ACMer，<br/>努力中的小菜鸡，<br/>想要自信和一往无前的勇气。