计数与递推

发表于 | 分类于 | 阅读次数:

##公式

排列组合

排列公式 $\displaystyle P(n,k)=\frac{n!}{(n-k)!}$

组合公式 $\displaystyle C(n,k)=\frac{P(n,k)}{P(k,k)}=\frac{n!}{(n-k)!k!}$

组合公式的性质

  • $C(0,0)=C(n,0)=C(n,n)=1$
  • $C(n,k)=C(n,n-k)$
  • $C(n,k)=C(n-1,k)+C(n-1,k-1)$
  • $\displaystyle C(n,k)=C(n,k-1)\cdot(n-k+1)/k$

递推

Catalen 数

引例：给一个凸 $n$ 边形，用 $n-3$ 条不相交的对角线把它分成 $n-2$ 个三角形，求不同的方法数目。

$f(n)=f(2)f(n-1)+f(3)f(n-3)+\dots+f(2)f(n-1),\quad f(2)=f(3)=1$

由另一种思路可得 $f(n)=f(2)$

##题目

[LA5846] Neon Sign

圆周上有 $n$ 个点，两两相连，染成两种颜色，求三边颜色相同的三角形的个数。

$n\leq1000$

由于是圆上的点，也就是说没有三点贡献的情况，则三角形总数 $n(n-1)(n-2)$

我们发觉单色三角形个数并不好统计，所以我们考虑统计费单色三角形的个数，若某个点连接的边有 $a_i$ 条边是以综合和那个颜色，有 $n-1-a_i$ 是另外一种颜色，那么非单色三角形就有 $\displaystyle\frac{1}{2}\sum_{i=1}^na_i(n-1-a_i)$ ，答案为 $\displaystyle n(n-1)(n-2)-\frac{1}{2}\sum_{i=1}^na_i(n-1-a_i)$

###[UVA11538] Chess Queen

国际象棋中，在同一行、列、对角线上的皇后是可以互相攻击的，求在 $n\times m$ 的棋盘上摆放两个可以互相攻击的皇后的方法数。

$n,m\leq10^6$

首先，在同一行的方案数很容易想到： $nm(m-1)$ ，那么同一列的就是 $mn(n-1)$

对于对角线上的情况，我们发现对角线的长度依次为：
$$
1,2,3,\dots,n-1,n\dots m-n+1 \text{ times}\dots,n,n-1,n-2,\dots,2,1
$$
考虑到对角线有两个方向，需要乘 $2$
$$
2\left(2\sum_{i=1}^{n-1}i(i-1)+(m-n+1)n(n-1)\right)=\frac{2n(n-1)(3m-n-1)}{3}
$$
那么答案为
$$
mn(m+n-2)+\frac{2n(n-1)(3m-n-1)}{3}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned long long ull;

int main()
{
	ull n,m;
	while(cin>>n>>m)
	{
		if(!n&&!m) break;
		if(n>m) swap(n,m);
		cout<<n*m*(m+n-2)+2*n*(n-1)*(3*m-n-1)/3<<endl;
	}
	return 0;
}

###[UVA11401] Triangle Counting

给定正整数 $n$ ，求边长为不大于 $n$ 的不同正整数的三角形的个数。

$n\leq10^6$

设最大边长为 $a$ 的三角形有 $f(a)$ 个，另外两条边为 $b,c$ ，则有 $b+c>x$ ，所以 $a-b<c<a$

可以暂时认为 $f_y$ 是一个等差数列，$\displaystyle f_b=0+1+2+3+\dots+(a-2)=\frac{(a-1)(a-2)}{2}$

然而这样我们计算了 $b=c$ 的情况，由于 $\displaystyle b\in\left[\left\lfloor\frac{a}{2}\right\rfloor+1,a-1\right]$ ，则需要减去 $\displaystyle\left\lfloor\frac{a-1}{2}\right\rfloor$

又由于 $b,c$ 的对称性，还需要除以 $2$

则
$$
f(a)=\frac{1}{2}\left(\frac{(a-1)(a-2)}{2}-\left\lfloor\frac{a-1}{2}\right\rfloor\right)
$$
而最长的边可以在 $[1,n]$ 之间的整数中选择，故答案为 $\displaystyle ans(n)=\sum_{i=1}^nf(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int MAXN=1e6;

ll f[MAXN+5];
inline void preTab()
{
	for(ll i=4;i<=MAXN;i++) 
		f[i]=f[i-1]+((i-1)*(i-2)/2-(i-1)/2)/2;
}
int main()
{
	preTab();
	int n;
	while(cin>>n)
	{
		if(n<3) break;
		cout<<f[n]<<endl;
	}
	return 0;
}

[UVA11806] Cheerleaders

在一个 $m\times n$ 的矩形网格中放 $k$ 个相同的石子，要求每个格子例最多放一个，石子必须用完，且第一行、最后一行、第一列、最后一列都要放石子。

$T\leq50,2\leq m,n\leq20,k\leq500$

如果没有最后一个条件的限制，答案可以很轻易用组合公式求出。有了限制之后可以考虑容斥原理，二进制枚举即可。

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
#include<iostream>
#include<cstdio>

const int MAXK=500,P=1e6+7;

int n,m,k;

int C[MAXK+5][MAXK+5];
inline void preTab()
{
	int i,j;
	C[0][0]=1;
	for(i=1;i<=MAXK;i++)
	{
		C[i][0]=C[i][i]=1;
		for(j=1;j<i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
	}
}

int main()
{
	preTab();
	int Case,T;scanf("%d",&T);
	for(Case=1;Case<=T;Case++)
	{
		int ans=0;
		scanf("%d%d%d",&n,&m,&k);
		for(int S=0;S<16;S++)
		{
			int cnt=0,r=n,c=m;
			if(S&1) r--,cnt++;if(S&2) r--,cnt++;
			if(S&4) c--,cnt++;if(S&8) c--,cnt++;
			if(cnt&1) ans=(ans-C[r*c][k]+P)%P;
			else ans=(ans+C[r*c][k])%P;
		}
		printf("Case %d: %d\n",Case,ans);
	}
	return 0;
}

###[POJ1737] Connected Graph

给定正整数 $n$ ，求有 $n$ 个节点的连通图个数。

$n\leq 50$

直接计算答案并不容易，我们考虑求出所有的可能性后减去不连通的个数。

设 $f(n)$ 为 $n$ 个节点的连通图个数（答案）， $g(n)$ 为 $n$ 个节点的非连通图个数， $h(n)$ 为 $n$ 个节点的图的个数。

对于 $h(n)$ ，一张 $n$ 个节点的图中最多有 $\frac{n\times(n-1)}{2}$ 条边，每条边都可以选或不选，根据乘法原理： $h(n)=2^{n\times(n-1)/2}$

接下来我们希望找到一个递推式。

考虑 $g(n)$ 的求法，对于一号节点，枚举其所在连通块的节点数 $i$ ，那么有 $\binom{n-1}{i-1}\cdot f(i)\cdot h(n-i)$ 种，求和即可。

由于显而易见的结论： $f(n)+g(n)=h(n)$

那么可得：
$$
f(n)=h(n)-\sum_{i=1}^{n-1}\binom{n-1}{i-1}f(i)h(n-i)
$$

用 python 计算后我们发现结果很长，所以需要用高精度。

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
#include<iostream>
#include<cstdio>
#include<cstring>

const int MAXN=55;

struct BN
{
	int num[1005],len;
	BN(int x=0)
	{
		len=0;
		memset(num,0,sizeof(num));
		if(x) len--;
		while(x) num[++len]=x%10,x/=10;
	}
};
BN operator +(BN a,BN b)
{
	BN res;res.len=std::max(a.len,b.len);
	for(int i=0;i<=std::max(a.len,b.len);i++)
	{
		res.num[i]+=a.num[i]+b.num[i];
		if(res.num[i]>=10)
			res.num[i]-=10,res.num[i+1]++;
	}
	while(true)
	{
		res.num[res.len+1]+=res.num[res.len]/10,res.num[res.len]%=10;
		if(res.num[res.len+1]) res.len++;
		else break;
	}
	return res;
}
BN operator -(BN a,BN b)
{
	BN res;res.len=std::max(a.len,b.len);
	for(int i=0;i<=std::max(a.len,b.len);i++)
	{
		res.num[i]+=a.num[i]-b.num[i];
		if(res.num[i]<0)
			res.num[i]+=10,res.num[i+1]--;
	}
	while(!res.num[res.len]) res.len--;
	return res;
}

BN t[1005];
BN operator *(BN a,BN b)
{
	int i,j;
	for(i=0;i<=a.len;i++) t[i]=BN();
	for(i=0;i<=a.len;i++)
	{
		for(j=0;j<=b.len;j++)
			t[i].num[i+j]=a.num[i]*b.num[j];
		for(j=0;j<=b.len;j++)
			t[i].num[i+j+1]+=t[i].num[i+j]/10,t[i].num[i+j]%=10;
		t[i].len=i+b.len; 
		while(true)
		{
			t[i].num[t[i].len+1]+=t[i].num[t[i].len]/10,t[i].num[t[i].len]%=10;
			if(t[i].num[t[i].len+1]) t[i].len++;
			else break;
		}
	}
	BN res;
	for(i=0;i<=a.len;i++) res=res+t[i];
	return res;
}

BN qpow(BN x,int n)
{
	int i;
	BN res=BN(1);
	for(i=1;i<=n;i<<=1,x=x*x)
		if(i&n) res=res*x;
	return res;
}

BN f[MAXN],C[MAXN][MAXN],h[MAXN];

inline void initTab()
{
	int i,j;
	for(i=0;i<MAXN;i++) 
		h[i]=qpow(BN(2),i*(i-1)/2);
	C[0][0]=BN(1);
	for(i=0;i<MAXN;i++)
	{
		C[i][0]=C[i][i]=BN(1);
		for(j=1;j<i;j++)
			C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
	for(i=1;i<MAXN;i++)
	{
		f[i]=h[i];
		for(j=1;j<i;j++)
			f[i]=f[i]-(C[i-1][j-1]*f[j]*h[i-j]);
	}
}

void print(BN x)
{
	for(int i=x.len;i>=0;i--)
		putchar(x.num[i]+'0');
}

int main()
{
	int i,n;
	initTab();
	while(scanf("%d",&n)!=EOF&&n)
	{
		print(f[n]);
		putchar('\n');
	}
}

[2017.08.25] 锦标赛游戏

有 $n​$ 个人进行循环赛，每两人进行比赛的胜率平分。如果两个人互相直接或间接赢过对方，那么成这两人水平相当。对于一个人，若有 $k​$ 个人与其水平相当，那么可以获得 $d_i​$ 奖金。求选手中期望奖金的最大值对 $998244353​$ 取模的结果。

$n\leq3000$

设 $f[n]$ 为所有种类的竞赛图的所有点的期望奖金之和，由于一种竞赛图中的所有点等价，所以所有种类的竞赛图中所有的点求平均即为答案。

设
$$
h(n)=2^{\frac{n(n-1)}{2}}
$$
则
$$
f(n)=\sum_{i=1}^n\binom{n}{i}g(i)(f(n-i)+h(n-i)d_i\cdot i)
$$

$$
\begin{align}
h(n)&=\sum_{i=1}^n\binom{n}{i}h(n-i)g(i)\
g(n)&=h(n)-\sum_{i=1}^{n-1}\binom{n}{i}h(n-i)g(i)
\end{align}
$$

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
#include<iostream>
#include<cstdio>
typedef long long ll;
const int MAXN=3e3+5,P=998244353;

int n;
int d[MAXN],f[MAXN],g[MAXN],ans[MAXN];

int C[MAXN][MAXN],pow2[MAXN*(MAXN-1)/2];
inline void preTab()
{
	int i,j;C[0][0]=1;
	for(i=1;i<=n;i++)
	{
		C[i][0]=C[i][i]=1;
		for(j=1;j<i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
	}
	pow2[0]=1;
	for(i=1;i<=n*(n-1)/2;i++) pow2[i]=pow2[i-1]*2%P;
}

int qpow(int x,int y)
{
	int res=1;
	for(ll i=1;i<=y;i<<=1,x=(ll)x*x%P)
		if(y&i) res=(ll)res*x%P;
	return res;
}

int inv(int x){return qpow(x,P-2);}

int main()
{
	freopen("tournament.in","r",stdin);
	freopen("tournament.out","w",stdout);
	int i,j;
	scanf("%d",&n);
	preTab();
	for(i=1;i<=n;i++) scanf("%d",d+i);
	for(i=1;i<=n;i++)
	{
		g[i]=pow2[i*(i-1)/2];
		for(j=1;j<i;j++) g[i]=(g[i]-(ll)g[j]*C[i][j]%P*pow2[(i-j)*(i-j-1)/2]%P+P)%P;
	}
	for(i=1;i<=n;i++) for(j=1;j<=i;j++)
		f[i]=(f[i]+(ll)g[j]*C[i][j]%P*(f[i-j]+(ll)d[j]*j%P*pow2[(i-j)*(i-j-1)/2]%P)%P)%P;
	for(i=1;i<=n;i++) ans[i]=(ll)f[i]*inv(i)%P*inv(pow2[i*(i-1)/2])%P;
	for(i=1;i<=n;i++) printf("%d\n",ans[i]);
}