题目链接:传送门

题解:

  设定dp[i][j]在深度为i下,使用j个节点的方案数

  显然的转移方程组就是 dp[h][n] = dp[h-1][i] * dp[h-1][n-i-1] + 2*dp[h-1][i]*dp[h-2][n-i-1];

  卷积形式

  利用FFT加速求解dp[h]

下面是AC代码

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
typedef unsigned long long ULL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N = 7e5+, M = 1e3+,inf = 2e9; const long long P=786433LL,mod = 786433LL;
const LL G=10LL; LL mul(LL x,LL y){
return (x*y-(LL)(x/(long double)P*y+1e-)*P+P)%P;
}
LL qpow(LL x,LL k){
LL ret=;
while(k){
if(k&) ret=mul(ret,x);
k>>=;
x=mul(x,x);
}
return ret;
}
LL wn[];
void getwn(){
for(int i=; i<=; ++i){
int t=<<i;
wn[i]=qpow(G,(P-)/t);
}
} int len;
void NTT(LL y[],int op){
for(int i=,j=len>>,k; i<len-; ++i){
if(i<j) swap(y[i],y[j]);
k=len>>;
while(j>=k){
j-=k;
k>>=;
}
if(j<k) j+=k;
}
int id=;
for(int h=; h<=len; h<<=) {
++id;
for(int i=; i<len; i+=h){
LL w=;
for(int j=i; j<i+(h>>); ++j){
LL u=y[j],t=mul(y[j+h/],w);
y[j]=u+t;
if(y[j]>=P) y[j]-=P;
y[j+h/]=u-t+P;
if(y[j+h/]>=P) y[j+h/]-=P;
w=mul(w,wn[id]);
}
}
}
if(op==-){
for(int i=; i<len/; ++i) swap(y[i],y[len-i]);
LL inv=qpow(len,P-);
for(int i=; i<len; ++i) y[i]=mul(y[i],inv);
}
}
LL dp[][N],tmp[N];
int n,h;
int main() {
freopen("avl.in", "r", stdin);
freopen("avl.out", "w", stdout);
getwn();
scanf("%d%d",&n,&h);
dp[][] = ,dp[][] = ,dp[][] = ;
len = ;
for(int i = ; i <= h; ++i) {
len = (<<(i+));
NTT(dp[i-],);NTT(dp[i-],);
for(int j = ; j < len; ++j)
tmp[j] = (dp[i-][j] * dp[i-][j])%mod;
NTT(tmp,-);
for(int j = ; j < len; ++j)
dp[i][j] = 2LL*tmp[j-] % mod;
for(int j = ; j < len; ++j)
tmp[j] = (dp[i-][j] * dp[i-][j])%mod;
NTT(tmp,-);
for(int j = ; j < len; ++j)
dp[i][j] += tmp[j-], dp[i][j] %= mod;
NTT(dp[i-],-);
NTT(dp[i-],-);
}
printf("%lld\n",dp[h][n]);
return ;
}

最新文章

  1. word20161221
  2. 长宽广州地区DNS
  3. bzoj4316: 小C的独立集
  4. URAL 2068 Game of Nuts (博弈)
  5. C++面试题:++i和i++哪个效率高?
  6. WinForm 进程和线程
  7. firstElementChild&amp;&amp;firstChild
  8. linux常用命令 wc统计命令
  9. Resources$NotFoundException资源文件没有找到
  10. redis设计原则
  11. May 30. 2018 Week 22nd Wednesday
  12. Fail2ban 配置
  13. PAT甲题题解-1128. N Queens Puzzle (20)-做了一个假的n皇后问题
  14. 创建 shiny 应用程序
  15. ZooKeeper典型使用场景一览
  16. lvs、haproxy、nginx 负载均衡的比较分析(转)
  17. 【CF453D】 Little Pony and Elements of Harmony(FWT)
  18. 四十五 常用内建模块 hashlib
  19. Pycharm上python和unittest两种姿势傻傻分不清楚【转载】
  20. POJ1274:The Perfect Stall(二分图最大匹配 匈牙利算法)

热门文章

  1. 九度oj 题目1100:最短路径
  2. 自动化运维之shell通配符,转义符,和元字符(二)
  3. iOS第三方网络图片加载- SDWebImage笔记(转)
  4. 【bzoj4889】[Tjoi2017]不勤劳的图书管理员 树状数组+分块+二分
  5. Mybatis 如何自动生成bean dao xml 配置文件 generatorconfig.xml (main()方法自动生成更快捷)
  6. 使用腾讯互动直播 遇到的坑 &#39;GLIBC_2.14&#39; not found 问题解决
  7. 标准C程序设计七---30
  8. ajax 分页(jquery分页插件pagination) 小例1
  9. css3 nth-child 与 nth-of-type 的区别
  10. 大话Spark(3)-一图深入理解WordCount程序在Spark中的执行过程