组合计数学习笔记

组合计数整合

8.14：模拟赛组合计数又寄，积累还是不够。
8.24：谢拜龚神讲解

VJ大专题

谢拜龚神

括号有关问题

P3058 [USACO12NOV] Balanced Cow Breeds G/S

对于括号类问题，研究其合法性时，一个重要的性质就是这一路过来都合法（和栈类似）。

套路地，将 \(\texttt{(}\) 看做 \(+1\)，\(\texttt{)}\) 看做 \(-1\)，那么该序列合法就是其所有前缀和都 \(\ge 0\)。设计 \(dp\)，\(dp[i][j][k]\) 表示标记了前 \(i\) 个数，\(A\) 序列的前缀和为 \(j\)，\(B\) 序列的前缀和为 \(k\)，的方案数。

\[dp[i][j][k] = dp[i-1][j-a[i]][k] + dp[i-1][j][k-a[i]] \]

这里自然保证了 \(j,k \ge 0\)。

但是时间复杂度是 \(O(n^3)\)。

观察到 \(j+k = sum\) 这一特征，即 \(i,j\) 已知足以只 \(k\)。

去掉 \(k\) 这一维，有转移：

\[dp[i][j] = dp[i-1][j-a[i]] + dp[i-1][j] \]

这里保证 \(sum-j \ge 0\) 即可。

CODE

#include<bits/stdc++.h>
using namespace std;
const int mod = 2012;
char s[1010];
int n,a[1010],f[1010][1010];
inline int add(int x,int y){ return x + y >= mod ? x + y - mod : x + y; }
inline void toadd(int &x,int y){ x = add(x,y); }
int main(){
	scanf("%s",s+1);
	n = strlen(s+1);
	for(int i = 1;i<=n;++i){
		if(s[i] == '(')a[i] = 1;
		else a[i] = -1;
	}
	f[0][0] = 1;
	for(int i = 1,sum = 0;i<=n;++i){
		sum += a[i];
		for(int j = 0;j<=sum;++j){
			f[i][j] = f[i-1][j];
			if(sum - j >= 0)toadd(f[i][j],f[i-1][sum-j]);
		}
	}
	printf("%d",f[n][0]);
	return 0;
}

P3059 [USACO12NOV] Concurrently Balanced Strings G

同上题类似，应当满足 \(sum_{l-1} = sum_r,sum_i \le sum_r(i ∈ [l,r-1])\)。

对于第二条式子，对于每个 \(l\)，找到第一个不满足的 \(r\)，就可以确定位置范围，再让第一条去限定即可。

但是对每个 \(l\) 而言会有多个 \(r\) 满足条件，我们发现对于满足条件的 \(r1,r2\)，两边是相互独立且都合法的，那么方案数就有了继承关系 \(g_{r2} + 1 \to g_{r1}\)。那么我们找到最左边的即可。

我们这个前缀序列的性质就是每次只会 \(+1,-1\)，故第一个小于 \(sum\) 的位置，其值一定为 \(sum-1\)，那么倒着扫的同时维护即可。

对于第一条式子，应当快速判断信息相同，故对每列做哈希，可以使用 map。

CODE

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod1 = 1e9 + 7, mod2 = 1e9 + 9, bas = 50000;
int n,k;
char s[50010];
int sum[15][50010];
ll hsh1[50010],hsh2[50010];
int pos[50010 << 1], lim[50010],r[50010];
ll f[50010];
struct Donny {
	size_t operator () (pair<ll, ll> donny) const {
		return donny.first * 111ll + donny.second;
	}
};
unordered_map<pair<ll, ll>, int, Donny> mp;
int main(){
	scanf("%d%d",&k,&n);
	for(int i = 1;i<=k;++i){
		scanf("%s",s+1);
		for(int j = 1;j<=n;++j){
			if(s[j] == '(')sum[i][j] = sum[i][j-1] + 1;
			else sum[i][j] = sum[i][j-1] - 1;
			hsh1[j] = (hsh1[j]*133%mod1+sum[i][j])%mod1;
			hsh2[j] = (hsh2[j]*133%mod2+sum[i][j])%mod2;
		}
	}
	memset(lim,0x3f,sizeof lim);
	for(int i = 1;i<=k;++i){
		memset(pos,0x3f,sizeof pos);
		for(int j = n;j;--j){
			pos[sum[i][j] + bas] = j;
			lim[j] = min(lim[j],pos[sum[i][j-1] - 1 + bas]);
		}
	}
	for(int i = n;i;--i){
		r[i] = mp[{hsh1[i-1],hsh2[i-1]}];
		mp[{hsh1[i],hsh2[i]}] = i;
	}
	ll ans = 0;
	for(int i = n;i;--i){
		if(r[i] && r[i] < lim[i]){
			f[i] = f[r[i]+1] + 1;
			ans += f[i];
		}
	}
	printf("%lld",ans);
	return 0;
}

总结：

看到快速判断信息相同，可做哈希。
括号序列转前缀和的一个性质：相邻值变化为 \(1\)。
对于有效信息的提取有利于优化 \(dp\)。

排列有关问题，二项式反演

CF1516E Baby Ehab Plays with Permutations

树相关

无标号有根树：LOJ6185 烷基计数

有重复组合数：\(C_{n+m-1}^m\)。（若在 \(n\) 种元素中有重复的选择 \(m\) 个元素的公式）

令 \(i \le j \le p\)，
\(k = 1 + i + j + p\)

\[f[k] = \begin{cases} [i = j = p] C(f[i]+3-1,3) \\ [i = j] C(f[i]+2-1,2) * f[p] \\ [j = p] C(f[j]+2-1,2) * f[1] \\ [other] f[i] * f[j] * f[p] \\ \end{cases} \]

这样转移时间复杂度为 \(O(n^3)\)。

f[0] = 1;
for(int k = 1;k<=n;++k){
  for(int i = 0;i<=k;++i){
  	for(int j = i;j<=k;++j){
	  int p = k - 1 - i - j;
		if(p < j)break;
		  if(i == j && j == p)toadd(f[k],mul(mul(mul(f[i]+2,f[i]+1),f[i]),inv6));
	          else if(i == j)toadd(f[k],mul(f[p],mul(mul(f[i]+1,f[i]),inv2)));
		  else if(j == p)toadd(f[k],mul(f[i],mul(mul(f[j]+1,f[j]),inv2)));
		  else toadd(f[k],mul(f[i],mul(f[j],f[p])));
		}
	}
}
printf("%d",f[n]);

考虑优化。

\(f[i][j]\) 表示子树大小为 \(i\)，根节点度数为 \(j\) 的方案数。

与之前直接枚举子树大小的方法不同，我们通过不断地插入子树来实现优化。

\(tot = ∑_{i=0}^{3} f[siz][i]\)
\(f[i][j] = f[i-siz \cdot k][j-k] \times C(tot+k-1,k)\)

f[1][0] = 1;
for(int siz = 1;siz<n;++siz){
  int now = 0;
  for(int i = 0;i<4;++i)toadd(now,f[siz][i]);
    for(int i = n;i;--i)
      for(int j = 1;j<4;++j)
      for(int k = 1;k<=j && siz*k<i;++k)
	  toadd(f[i][j],mul(f[i-siz*k][j-k],C(now+k-1,k)));
} 
int ans = 0;
for(int i = 0;i<4;++i)toadd(ans,f[n][i]);
printf("%d",ans);

时间复杂度 \(O(n^2 m)\)。

无标号无根树：BZOJ4271 烷烃计数。

对于无根树的一个套路就是将其重心作为根。

那么同上道题，直接预处理出相同的东西。
但是要限制插入的子树大小 \(\le (n+1)/2\)，这样就可以保证了根节点为重心。

一个重心：\(∑_{i=0}^{4}f[n][i]\)；
两个重心：此时一定是偶数个节点，这里又要用到有重复组合数，即 \(C(sum+2-1,2)\)，其中 \(sum = ∑_{i=0}^{3}f[n/2][i]\)。

由于数据范围中 \(n \le 500\)，大致估一下：组合数 \(500^4\)，三维前缀和 \((500^4)^4\)，要用高精度。（这里不太清晰，多请指正）。

此处高精度代码省去。

#include<bits/stdc++.h>
#define print(a) cerr<<#a"="<<(a)<<endl
using namespace std;
const int N = 510,bas = 1e4;
int n;
NUM C(NUM n,int m){
	NUM d(1);
	int t = m;
	NUM res(1);
	while(t--){
		res = res * n;
		n = n - d;
	}
	for(int i = 1;i<=m;++i)res = res / i;
	return res;
}
void init(){
	f[1][0] = NUM(1);
	for(int siz = 1;siz<=(n-1)/2;++siz){
		NUM now;
		for(int i = 0;i<4;++i)now = now + f[siz][i];
		for(int i = n;i;--i){
			for(int j = 1;j<=4;++j)
				for(int k = 1;k<=j && siz*k<i;++k)
					f[i][j] = f[i][j] + f[i-siz*k][j-k] * C(now+(k-1),k);
		}
	}
}
int main(){
	scanf("%d",&n);
	init();
	NUM ans;
	for(int i = 0;i<=4;++i)ans = ans + f[n][i];
	if(!(n&1)){
		NUM sum(0);
		for(int i = 0;i<=3;++i)sum = sum + f[n/2][i];
		ans = ans + C(sum+1,2);
	}
	ans.output();
	return 0;
}

标签：le,前缀,组合,50010,int,sum,笔记,计数,dp
From： https://www.cnblogs.com/fight-for-humanity/p/18357516