agc022F

题目大意

题解

非常玄学的dp

首先一个很显然的东西，因为把x按照y翻转得到2y-x，所以每个点的最终系数为±2^k

假设有两种不同的方案得到同样的接，那么相减之后把正的放一边负的放另一边，因为10^100非常大以至于把其他的加在一起都不行，因此只要方案不同答案就不同

转化模型，从y向x连一条边，变成一个由有向边构成的树，每次选一条边u->v，把u所在连通块*2，v所在连通块取反

可以写成一棵权值为2^深度的树，然后从后往前选边，考虑dp，然后就不会了

网上有各种玄学做法，根据个人理解讲一下比较常见的那种

---

一个点的权值=(-1)^(儿子个数+某个祖先在选完相连链之后选的儿子个数)，这样会好考虑一些

由于一个点的权值只会和儿子和祖先有关，因此在最后一层加上一个点后向上只会影响到其父亲，向下的影响等价于放之前父亲祖先的影响，即把点权设为父亲当前的点权，然后把父亲以及之前加入的兄弟节点取反

设f[i,j]表示已经放了i个点，最后一层有j个儿子个数为奇数的方案

假设一个点有s个儿子，那么有s/2上取整（网上的都写成了下取整）个点和父亲不同

枚举当前层的点数k，有(j+k)/2个点与父亲不同

再枚举实际不同的个数l，那么新放的这一层有|l-(j+k)/2|个奇点，乘的系数是C(i+k,i)*C(k,l)

以上是网上的题解，下面开始个人看法

---

首先如果是简单的“不同”，那么实际上+,-变成-+-,+-的时候当不同个数为2时有+++,+-以及---,--两种情况，这两种都要算进去，这里感觉非常奇怪

并且更加奇怪的是，不同的个数为什么可以直接丢到组合数里面算

所以状态f[i,j]中的j，实际表示的应该是有j个同一种符号奇点的方案数，符号是硬点的某一种（+或-都可以），并且可以改变，具体见下文

还是上面的例子，+,-变成-+-,+-，因为奇点是+所以硬点的符号是+

所以枚举的l的实际意义是当前硬点的符号的个数，由于奇点符号全部相同，所以如果不变（下一层奇点为0）的话那个数就是(j+k)/2，变了之后下一层的奇点个数就是|l-(j+k)/2|

这样就可以在l=0以及l=4把上面的情况区分开来，同时由于l表示的是符号个数所以可以直接组合数

观察一下，如果l>(j+k)/2的话那么是把非硬点符号改成硬点符号，<(j+k)/2是把硬点符号改成非硬点符号，因为改的符号相同且改过的都是奇点，所以下一层的符号就是改过之后的符号，也是唯一确定的

如此归纳下去，最后得到的就是正确的结果

END

时间复杂度O(n^4)

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define C(n,m) ((jc[n]*Jc[m])%1000000007*Jc[(n)-(m)]%1000000007)
#define add(a,b) a=((a)+(b))%1000000007
#define abs(x) ((x)>0?(x):-(x))
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define mod 1000000007
#define Mod 1000000005
#define ll long long
//#define file
using namespace std;

ll f[51][51],jc[51],Jc[51];
int n,i,j,k,l,x;

ll qpower(ll a,int b) {ll ans=1; while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;}

int main()
{
	#ifdef file
	freopen("agc022f.in","r",stdin);
	#endif
	
	scanf("%d",&n);
	jc[0]=1;
	fo(i,1,n) jc[i]=jc[i-1]*i%mod;
	Jc[n]=qpower(jc[n],Mod);
	fd(i,n-1,0) Jc[i]=Jc[i+1]*(i+1)%mod;
	
	f[1][0]=f[1][1]=1;
	fo(i,1,n-1)
	{
		fo(j,0,i)
		{
			fo(k,max(1,j),n-i)
			{
				fo(l,0,k)
				if (!((j+k)&1))
				{
					x=(j+k)/2;
					add(f[i+k][abs(x-l)],f[i][j]*C(i+k,i)%mod*C(k,l));
				}
			}
		}
	}
	printf("%lld
",f[n][0]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}