省选模拟赛20200302 T3 LYK loves rabbits（思维题+DP）

 

 

题解

思维题

我们首先会发现，一种状态最多有三种方式可以转移到其他状态

1、中间的往左跳

2、中间的往右跳

3、两边的某一个往中间跳（最多一个可行，这个可以简单证明）

每个状态只有两度或三度，我们可以联想到二叉树

我们把往中间跳后的状态设为父亲，往左跳设为左儿子，往右跳设为右儿子

然后我们有一个发现，一个状态如果一直往中间跳，那么终止状态的三个坐标一定是一个等差数列

由于保证有解，我们可以知道两个状态到根的路径一定是有交集的

于是我们可以先找出它们在这个二叉树上的LCA（如果LCA需要走k步以上就直接无解了）

然后我们做一个树形DP

设两个状态分别为A和B

设f[i][j][k]表示当前点x（从A出发）到LCA(x,B)的距离为 i ，LCA(x,B)到B的距离为 j ，一共走了 k 步的方案数

那么当i！=0时（即 x 到 B 的路径需要拐弯（这里的拐弯指先向上再向下））

f[i][j][k]=f[i-1][j][k-1]+2*f[i+1][j][k-1]     （向上走，向下走）

当i=0时且j！=0时，我们有三种选择

f[i][j][k]=f[1][j][k-1]+f[0][j+1][k-1]+f[0][j-1][k-1] （向不含B的子树向下走一步，向上走一步，向B所在的子树向下走一步）

当i=0且j=0时，即已经走到了B点

f[i][j][k]=f[0][1][k-1]+2*f[1][0][k-1]   （向上走，向下走）

然后记忆化搜索DP一下即可，注意判一下边界

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 105
#define LL long long
const int mod=1000000007;
LL a[N],b[N],c[N];
LL x[N],y[N],z[N];
int f[N][N][N];
int K,k1,k2;
int F(int i,int j,int k)
{
	if(!i&&!j&&!k)return 1;
	if(!i&&j>k2)return 0;//
	if(i+j>k)return 0;
	if(f[i][j][k]!=-1)return f[i][j][k];
	if(!i){
		if(!j)f[i][j][k]=(F(0,1,k-1)+F(1,0,k-1)*2%mod)%mod;
		else f[i][j][k]=((F(0,j+1,k-1)+F(0,j-1,k-1))%mod+F(1,j,k-1))%mod;
	}
	else f[i][j][k]=(F(i-1,j,k-1)+F(i+1,j,k-1)*2%mod)%mod;
	return f[i][j][k];
}
int main()
{
	freopen("rabbits.in","r",stdin);
	freopen("rabbits.out","w",stdout);
	int i,j;
	scanf("%lld%lld%lld%lld%lld%lld%d",&a[0],&b[0],&c[0],&x[0],&y[0],&z[0],&K);
	while(k1<K){
		if(b[k1]-a[k1]==c[k1]-b[k1])break;
		if(b[k1]-a[k1]<c[k1]-b[k1])k1++,a[k1]=b[k1-1],b[k1]=2*b[k1-1]-a[k1-1],c[k1]=c[k1-1];
		else k1++,a[k1]=a[k1-1],b[k1]=2*b[k1-1]-c[k1-1],c[k1]=b[k1-1];
	}
	while(k2<K){
		if(y[k2]-x[k2]==z[k2]-y[k2])break;
		if(y[k2]-x[k2]<z[k2]-y[k2])k2++,x[k2]=y[k2-1],y[k2]=2*y[k2-1]-x[k2-1],z[k2]=z[k2-1];
		else k2++,x[k2]=x[k2-1],y[k2]=2*y[k2-1]-z[k2-1],z[k2]=y[k2-1];
	}
	bool p=1;
	for(i=0;i<=k1&&p;i++)for(j=0;j<=k2&&p;j++)
		if(a[i]==x[j]&&b[i]==y[j]&&c[i]==z[j])p=0; 
	i--;j--;
	memset(f,-1,sizeof(f));
	printf("%d\n",F(i,j,K));
}