「from CommonAnts」Codeforces 814E - An unavoidable detour for home 题解

liu_cheng_ao 2017-06-08 8:48:12 2017-06-08 8:49:55

以下是吐槽,建议跳过


昨天打了 Codeforces 好久不见的 CN Round,结果大翻车了…… 调E调了十几分钟调不出,最后发现……题目里有一句

No two roads connect the same pair of towns

我的内心是崩溃的……改1个字符就AC了好吗
一定要认真读题……
一定要认真读题……
一定要认真读题……


#### 以上是吐槽,建议跳过

结束后本来想找个人对下递推数组的,看了一圈结果发现……你们的数组怎么都这么多维啊 qwq
于是就赶在官方题解 update 之前先来闷声水一篇民间题解……

首先,由于最短路径的唯一性,图的 bfs 树中,不存在连接相邻两层的非树边,也即非树边只连接同一层内部。
并且每一层编号一定是连续的一段。这样,我们可以递推转移(因为只和上一层有关)。

f[i][j] 表示:

  • 考虑前 i 个点
  • 与第 i 个点到根距离相等的有 j
  • 到根距离小于第 i 个点的点的度数已满足
  • 到根距离等于第 i 个点的点只考虑bfs树上的父边

满足以上条件的方案数。
递推时,我们枚举上一层的点数 k 。我们发现,转移数取决于这 k 个点中度分别为 2 和 3 的点数,以及本层的点数。
g[i][j][k] 表示本层有 i 个点,上一层有 j 个度为 2 的点, k 个度为 3 的点的转移方案数。
则有:

f[i][j]=\sum_k f[i-j][k]\cdot g[j][c_2][c_3]

其中 c_2 c_3 分别表示这 k 个点中度分别为 2 和 3 的点数。

那么现在我们要求出 g 。通过依次枚举本层的点的连接方式,度为 2 的点的连接方式和度为 3 的点的连接方式,我们可以得到递推式:

g[i][j][k]=\begin{cases} 1& i=j=k=0\\ \sum_{l=2}^{k-1}g[i][j][k-l-1]\cdot \binom {k-1}{l} \cdot N_{l+1}& i=j=0,k> 0\\ (j-1)\cdot g[i][j-2][k]+k\cdot g[i][j][k-1]& i=0,j>0\\ j\cdot g[i-1][j-1][k]+k\cdot g[i-1][j+1][k-1]& i>0\\ 0 & \text{otherwise} \end{cases}

其中 N 表示项链数,即:

N_i= \begin{cases} 1 & i=2\\ \frac{(N-1)!}{2} & i>2\\ 0 & \text{otherwise} \end{cases}

于是我们就愉快地在 O(n^3) 时间内解决问题了。

代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>

using namespace std;
typedef long long LL;
const int MX=51,md=1000000007;
int n,d[MX];
int fac[MX],inv[MX],facinv[MX];

int f[MX][MX],g[MX][MX][MX];
#define C(x,y) ((LL)fac[x]*facinv[y]%md*facinv[x-y]%md)
void ini(){
	fac[0]=facinv[0]=1;
	inv[1]=1;for(int i=2;i<=n;i++)inv[i]=(LL)inv[md%i]*(md-md/i)%md;
	for(int i=1;i<=n;i++)fac[i]=(LL)fac[i-1]*i%md;
	for(int i=1;i<=n;i++)facinv[i]=(LL)facinv[i-1]*inv[i]%md;
	g[0][0][0]=1;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n-i;j++)if(i||j){
			if(!i){
				for(int k=2;k<j;k++)g[0][i][j]=(g[0][i][j]+(LL)g[0][i][j-1-k]*C(j-1,k)%md*((LL)fac[k]*inv[2]%md)%md)%md;
			}else{
				if(i>=2)g[0][i][j]=(g[0][i][j]+(LL)g[0][i-2][j]*(i-1)%md)%md;
				if(j>=1)g[0][i][j]=(g[0][i][j]+(LL)g[0][i][j-1]*j%md)%md;
			}
		}
	for(int i=1;i<n;i++){
		for(int s=0;s<n-i;s++){
			for(int k=0;k<=s;k++){
				int j=s-k;
				if(j||k){
					if(j)g[i][j][k]=(g[i][j][k]+(LL)g[i-1][j-1][k]*j%md)%md;
					if(k)g[i][j][k]=(g[i][j][k]+(LL)g[i-1][j+1][k-1]*k%md)%md;
				}
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&d[i]);
	ini();
	f[d[1]+1][d[1]]=1;
	for(int i=d[1]+2;i<=n;i++){
		for(int j=1;j<=i-d[1]-1;j++){
			int cl0=0,cl1=0;
			for(int k=1;k<i-j;k++){
				if(d[i-j-k+1]==2)cl0++;else cl1++;
				f[i][j]=(f[i][j]+(LL)g[j][cl0][cl1]*f[i-j][k]%md)%md;
			}
		}
	}
	int ans=0,cc0=0,cc1=0;
	for(int i=1;i<n;i++){
		if(d[n-i+1]==2)cc0++;else cc1++;
		ans=(ans+(LL)f[n][i]*g[0][cc0][cc1]%md)%md;
	}
	printf("%d\n",ans);
	return 0;
}

共 2 条回复

liu_cheng_ao

回楼上:这个题因为不能重边所以大小为 2 的环是不行的,也不能按项链数算。项链数在组合计数上有自己的定义。

wearry

i = 2 时, Ni = 0 才对吧? 这好像是您比赛时出的错。。。