佛山微信网站开发,东莞建站模板公司,wordpress更改图片上传路径,深圳福田区口岸社区正题
题目链接:https://jzoj.net/senior/#main/show/2755 题目大意
求有多少个nnn个点直径为ddd的标号树。 解题思路
定义fi,jf_{i,j}fi,j表示iii个点#xff0c;深度不超过jjj的标号树数量。
然后有转移fi,j∑k1i−1Ci−2k−1∗k∗fk,j−1∗fi−k,jf_{i,j}\sum_{k1}^{i…正题
题目链接:https://jzoj.net/senior/#main/show/2755 题目大意
求有多少个nnn个点直径为ddd的标号树。 解题思路
定义fi,jf_{i,j}fi,j表示iii个点深度不超过jjj的标号树数量。
然后有转移fi,j∑k1i−1Ci−2k−1∗k∗fk,j−1∗fi−k,jf_{i,j}\sum_{k1}^{i-1}C_{i-2}^{k-1}*k*f_{k,j-1}*f_{i-k,j}fi,jk1∑i−1Ci−2k−1∗k∗fk,j−1∗fi−k,j
然后对于输入我们考虑根节点就是直径经过的点那么我们分为两种情况讨论
ddd是奇数这个我们枚举两个树拼接在一起然后其它的点瞎连接即可ddd是偶数将两棵树拼接在一起即可那么答案为fn,d/2−fn,d/21?f_{n,d/2}-f_{n,d/21}?fn,d/2−fn,d/21?我们发现会有不合法情况把不合法情况减去就好了
要高精度 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N51,P1e6;
struct BNN{ll a[N],siz;
}ans,c[N][N],f[N][N],tmp;
BNN operator(BNN a,BNN b){for(ll i0;iN;i){a.a[i]a.a[i]b.a[i];a.a[i1]a.a[i]/P;a.a[i]%P;if(a.a[i])a.sizi;}return a;
}
BNN operator-(BNN a,BNN b){for(ll i0;iN;i){a.a[i]a.a[i]-b.a[i];while(a.a[i]0){a.a[i1]--;a.a[i]P;}if(a.a[i])a.sizi;}return a;
}
BNN operator*(BNN a,BNN b){BNN c;memset(c.a,0,sizeof(c.a));for(ll i0;ia.siz;i)for(ll j0;jb.siz;j)c.a[ij]a.a[i]*b.a[j];c.siz0;for(ll i0;iN;i){c.a[i1]c.a[i]/P;c.a[i]%P;if(c.a[i])c.sizi;}return c;
}
void write(BNN x){ll wN-1;while(w!x.a[--w]);printf(%lld,x.a[w]);while((--w)0){if(x.a[w]1e5)putchar(0);if(x.a[w]1e4)putchar(0);if(x.a[w]1e3)putchar(0);if(x.a[w]1e2)putchar(0);if(x.a[w]1e1)putchar(0);printf(%lld,x.a[w]);}putchar(\n);
}
int main()
{c[0][0].a[0]1;for(ll i1;iN;i){c[i][0].a[0]1;for(ll j1;ji;j)c[i][j]c[i-1][j]c[i-1][j-1];}for(ll i0;iN;i)f[1][i].a[0]1;for(ll n2;nN;n) for(ll d1;dN;d){if(dn) {f[n][d]f[n][d-1];continue;}for(ll i1;in;i){tmp.a[0]i;f[n][d]f[n][d](c[n-2][i-1]*tmp*f[i][d-1]*f[n-i][d]);n;n--; }}ll n,d;while(scanf(%lld%lld,n,d)!EOF){ll rd/2;if(nd){printf(0\n);continue;}if(!d){printf(%lld\n,(n1));continue;}if(!r){printf(%lld\n,(n2));continue;}memset(ans.a,0,sizeof(ans.a));ans.siz0;if(d1){for(ll ir;in;i){ll jn-2-i;if(jr) continue;ansans((f[i1][r]-f[i1][r-1])*(f[j1][r]-f[j1][r-1])*c[n-2][i]);}ansans*c[n][2];}else{ansf[n][r]-f[n][r-1];if(r2){for(ll ir;in-1;i){tmp.a[0]i;ansans-(tmp*(f[i][r-1]-f[i][r-2])*c[n-1][i]*f[n-i][r-1]);}}tmp.a[0]n;ansans*tmp;}write(ans);}
}
