计数进阶篇

http://www.zhengruioi.com/contest/746/problem/392

计数难,难于上青天

卡常计数难,随便切等于金牌稳

n个点无标号有根树直径等于某个值的树计数

首先我们考虑无标号有根树的计数递推

别跟我说什么 $n^{n-1}$

$f_i$ 表示i个点的有标号树方案数

转移考虑确定根的标号后,再去确定除了根的最小标号在哪颗子树?

然后转移就可以考虑枚举那个有最小标号的子树是多少个点,然后分配下现在的新标号....

f_n=n*\sum_j^nf_j*\frac{f_{n-j}}{n-j}*\binom{k-1}{n-2}

注意我们第一个n是分配了编号,然后后面除去的那项是我们不考虑他的根标号,在这一次重新分配了

注意到只要能快速合并信息就好,然后我们就能写出一个很牛逼的 $n^6$ ?的做法

$f_{i,j,k}$ 表示i个点,然后子树最大深度为j,直径为k的有根树方案数

f_{i,max(d1+1,d2),max(k1,k2,d1+1+d2)}=n*\sum_j^nf_{j,d1,k1}*\frac{f_{n-j,d2,k2}}{n-j}*\binom{k-1}{n-2}

于是你发现你很蠢,可以前缀和优化做到 $n^5$

但是还是很蠢哎,你发现既然第三维的合并这么简单,干脆直接在外层枚举就好了!

即,在外层枚举一个最大直径,然后里层只有两维,合并时满足 $d1+d2+1<Lmax$

dp得到的结果是小于等于这个最大的直径的,我们再钦点他差分就是每个答案了

这个正确性就显然吧?qwq $O(n^5)$ 前缀和优化 $O(n^4)$

然后还是很蠢啊,因为我们每次多一个直径就重做一遍.....

想想,我们多出的复杂度在于重复计算,那么如果我们只算多出去的直径呢??

问题的本质是不是在于合并这个子树时候啊?

于是一个直接统计每个深度的神仙std出现了

还是 $f_{i,j}$ 表示i个点最大深度为j的(前缀和意义)有根树方案数

然后 $g_{i,j}$ 表示i个点最大深度是j的有根树方案数,不难发现就是f数组的一个差分

于是我们可以来统计了,首先看直径长度为奇数的,此时中间是一条边,设直径为2L+1

ans=\sum_{j}g_{j,L}*g_{n-j,L}*\binom{k-1}{n-1}

相当于两棵树拼起来

因为我们左右两边可能分不清,但是我们确定了根就能确定最小标号所在子树,所以不妨钦点最小标号在的子树是左边那个

偶数,中间是一个点,我们要求最大深度L的子树至少出现两次

ans=g_{n,l}-\sum_{j}g_{j,l-1}*f_{n-j,l-1}*\binom{k}{n}

这个也是很显然的,我们g数组只能保证出现了一次,却不能保证出现多次,于是我们减去一下出现一次的方案

而出现一次,可以是一个深度小于等于L-1树根上并上一个最大深度为L-1的子树,这样这个根只有一个L-1的大小

而我们这两棵树是本质不同的....所以说只需要给其中一个分配上标号即可

感性理解一下,最后统计答案的时候我们把有根树变成无根树了,因为没有给根分配标号啊

这份代码只有90,因为100要卡常,把转移式子变成两项乘积...

code:


//首先有根树计数?
//f_i表示i个点的有根树
//然后转移f_i=n*\sumf_k * f_{n-k}/n-k *\binom{k-1}{n-2}
//然后我们发现这个式子是可以推广的
//先冲个暴力吧
//f_{i,j}表示i个点,然后深度至少为j的方案数
//外层枚举直径计算方案就优化一下,然后差分即可
//f_{n,j}=n*sumf_{k,j-1}*f_{n-k,j}/n-k*binom{k-1}{n-2}
//g数组就是f数组的差分数组qwq
//然后考虑计算答案,如果为偶数
//我们中间是一个点,那么我们要求最大深度子树出现两次,所以容斥
//钦点一个严格小于等于i-1的做根,然后另一个接在上面,是i qwq,而且只能有一个,不会有多个qwq
//g_{n,l/2}-sumkg_{k,l/2-1}*f_{n-k,l/2-1}*C_{n,k}
//如果是奇数
//\sumkg_{k,l/2}*g_{n-k,l/2}*C_{n-1,k-1}

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 507;
int n;
ll fac[MAXN], ifac[MAXN], C[MAXN][MAXN], inv[MAXN], P;
inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}
inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}
inline void init() {
	fac[0] = 1;
	for(int i = 1; i <= n; ++i)fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[n] = ksm(fac[n], P - 2);
	for(int i = n - 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
	ifac[1] = ifac[0] = 1;
	for(int i = 2; i <= n; ++i)inv[i] = ifac[i] * fac[i - 1] % P;
	inv[0] = 1;
	inv[1] = 1;
	C[0][0] = 1;
	for(int i = 1; i <= n; ++i) {
		C[i][0] = 1;
		for(int j = 1; j <= i; ++j) {
			add(C[i][j], C[i - 1][j - 1]);
			add(C[i][j], C[i - 1][j]);
		}
	}
	return ;
}

ll f[MAXN][MAXN], g[MAXN][MAXN], f1[MAXN][MAXN];

inline void solve1() {
	for(int i = 0; i <= n; ++i)f[1][i] = 1;
	for(int i = 0; i <= n; ++i)f1[1][i] = 1;
	for(int i = 2; i <= n; ++i) {
		for(int j = 1; j < i; ++j) {
			for(int k = 1; k < i; ++k) {
				add(f[i][j], f[k][j - 1] * f1[i - k][j] % P * C[i - 2][k - 1] % P);
			}
			f1[i][j] = f[i][j];
			f[i][j] = f[i][j] * i % P;
			g[i][j] = f[i][j];
			add(g[i][j], P - f[i][j - 1]);
		}
		for(int j = i; j <= n; ++j) {
			f[i][j] = f[i][j - 1];
			f1[i][j] = f1[i][j - 1];
		}
	}
	return ;
}

inline void solve2() {
	printf("0 ");
	for(int i = 1; i < n; ++i) {
		ll x = i >> 1;
		ll ans = 0;
		if(i & 1) {
			for(int k = 1; k <= n; ++k) {
				add(ans, C[n - 1][k - 1]*g[k][x] % P * g[n - k][x] % P);
			}
		} else {
			for(int k = 1; k <= n; ++k) {
				add(ans, P - C[n][k] * g[k][x - 1] % P * f[n - k][x - 1] % P);
			}
			add(ans, P);
			add(ans, g[n][x]);
		}
		printf("%lld ", ans);
	}
	puts("");
	return;
}

int main() {
	scanf("%d%lld", &n, &P);
	if(n == 1) {
		puts("1");
		return 0;
	}
	init();
	solve1();//预处理f,g数组
	solve2();//计算答案
	return 0;
}
/*
4 1000000007
*/

无标号有根树计数, $n<=1000$

生成函数做法都上天去吧

首先一开始口胡了一个可行的做法 $f_{i,j}$ 表示i个点最小子树至少为j的方案数

转移可以枚举一个大于j的子树,反正肯定可以,因为没有上一个可以钦点最小编号所以说这个是$O(n^3)d的

然后这样其实有一点蠢,虽然大小相同的子树本质相同,但是如果我们一次都确定好了不就行了吗?

$f_i$ 表示i个点的有根子树方案数

于是此时我们枚举一个最大子树的大小,以及这棵树有多少个最大子树

f_i=\sum_{s}^{i-1}\sum_{j}^{i/s}j*f_{s}*f_{n-s*j}$$??? 好像不行,因为无论如何都是整数划分.... 于是我们发现EI群内多次询问都没人给出解释,我们乖乖的接受生成函数推导出的式子 $$(n-1)f_n=\sum_{j}^{n-1}f_j\sum_{i|n-j}if_i

处理 $g_i=sum_{i|k}f_k$ 即可做到 $n^2$

同样的,这个式子就可以做到无标号有根树直径计数了!!!

无根树的我们先不讨论,具体思想其实就是考虑只统计根在的一次

CSP.ac上一道计数题

$f_{i,j,k}$ 表示前i个数,现在用了j次操作,然后最后一段的值是k方案数

$g_{i,j,k}$ 表示前i个数,现在用了j次操作,然后最后一段的值小于等于k方案数

并且我们钦定这个转移次序是最优秀的,也就是说我们用最少的j次操作得到现在的状态

转移考虑枚举一个之前的数,然后把这些划分成一段

$f_{i,j,k}=\sum_{l<i,max_(l,i)<=k}g_{l,j-1,k}$

特别的,当li-1且kk时我们j一维不用减1

这样直接实现可以做到 $O(n^4)$

观察一下,我们实际上并不需要一次填一段数

$f_{i,j,k,0/1}$ 表示考虑了前i个数,然后最后一个数是k,用了j次操作,有没有从上一个数继承过来第j次操作的方案数

如果是0

转移我们只需要填前一个数,就是i-1位置上的,加上 $f_{i-1,j-1,h<k,0/1}$ 和 $f_{i-1,j,k,0/1}$

如果是1,也同理吧

这样做显然是对的,但是还是没有看清楚问题的本质qwq

你会发现,一个数成为最大值只有一段区间,而我们只需要按顺序考虑这一段区间的影响即可

$f_{i,j}$ 表示前i个数用了j次操作的方案数

转移考虑i这个数覆盖到的范围我们都更新一次!!并且把他们的dp值也相应修改

因为此时没有第三维,所以可能会出现重复更新状态的情况,不过只要含义是正确的最后结果也是对的

如果数列随机可以做1000的样子

code:(刻意卡常)


#include<bits/stdc++.h>
#define R register
using namespace std;
const int MAXN=500;
const int P=998244353;
int n,k,l[MAXN],r[MAXN],a[MAXN],f[MAXN][MAXN],sum,ans;
inline void add(int &x,int y) {x+=y;if(x>=P)x-=P;}
int main() {
	scanf("%d%d",&n,&k);
	for(R int i=1; i<=n; ++i)scanf("%d",&a[i]);
	for(R int i=1; i<=n; ++i) {l[i]=i,r[i]=i;for(l[i]=i; l[i]>1 && a[i]>a[l[i]-1]; --l[i]);for(r[i]=i; r[i]<n && a[i]>a[r[i]+1]; ++r[i]);}
	f[0][0]=1;
	for(R int i=1; i<=n; ++i) {
		for(R int j=k,sum; j>=1; --j) {
			add(f[i][j],f[i-1][j]);sum=0;
			for(int k=l[i]; k<=r[i]; ++k)add(sum,f[k-1][j-1]),add(f[k][j],sum);
			add(f[i][j],P-f[i-1][j-1]);
		}add(f[i][0],f[i-1][0]);
	}
	for(R int i=0; i<=k; ++i)add(ans,f[n][i]);	
	printf("%d\n",ans);
	return 0;
}

CF1444B

考场被无限降智

首先读错了题,变成了标准n^2....算不排序数组的答案????

p降序,q升序

然后我们再回到这个题

随便玩几组发现我们每次划分的贡献好像是....一样的???

因为将原序列排序后,无论如何一次划分的贡献都是前n大元素的和减去后n大元素的和

如果存在前n大元素之间相减,说明有一个位置i,满足有i个比他大的数,n-i个比他小的数

嗯,这样正好能推出一个数组有n+1长度

所以答案就是 $(sum-sum)*C_{n,2n}$

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+7;
const int P=998244353;
int n,m;
int a[MAXN];
ll S,fac[MAXN],ifac[MAXN],S2;

inline ll ksm(ll x,ll y) {
	ll ans=1;
	while(y) {
		if(y&1)ans=ans*x%P;
		x=x*x%P;
		y>>=1;
	}
	return ans;
}

int main() {
	scanf("%d",&n);
	m=2*n;
	for(int i=1; i<=m; ++i) {
		scanf("%d",&a[i]);
		S+=a[i];
	}
	sort(a+1,a+m+1);
	fac[0]=ifac[0]=ifac[1]=1;
	for(int i=1; i<=m; ++i) {
		fac[i]=fac[i-1]*i%P;
	}
	ifac[m]=ksm(fac[m],P-2);
	for(int i=m-1; i>=2; --i) {
		ifac[i]=ifac[i+1]*(i+1)%P;
	}
	for(int i=1; i<=n; ++i)S2+=a[i];
	S-=S2;
	S-=S2;
	S%=P;
	printf("%lld\n",S*fac[m]%P*ifac[n]%P*ifac[n]%P);
	return 0;
}

夏晓光(loveJY)的博客

CSP-S2周末刷题班（第一场）