Gym - 100341C FFT优化DP
2024-09-07 08:39:09
题目链接:传送门
题解:
设定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 ;
}
最新文章
- word20161221
- 长宽广州地区DNS
- bzoj4316: 小C的独立集
- URAL 2068 Game of Nuts (博弈)
- C++面试题:++i和i++哪个效率高?
- WinForm 进程和线程
- firstElementChild&;&;firstChild
- linux常用命令 wc统计命令
- Resources$NotFoundException资源文件没有找到
- redis设计原则
- May 30. 2018 Week 22nd Wednesday
- Fail2ban 配置
- PAT甲题题解-1128. N Queens Puzzle (20)-做了一个假的n皇后问题
- 创建 shiny 应用程序
- ZooKeeper典型使用场景一览
- lvs、haproxy、nginx 负载均衡的比较分析(转)
- 【CF453D】 Little Pony and Elements of Harmony(FWT)
- 四十五 常用内建模块 hashlib
- Pycharm上python和unittest两种姿势傻傻分不清楚【转载】
- POJ1274:The Perfect Stall(二分图最大匹配 匈牙利算法)
热门文章
- 九度oj 题目1100:最短路径
- 自动化运维之shell通配符,转义符,和元字符(二)
- iOS第三方网络图片加载- SDWebImage笔记(转)
- 【bzoj4889】[Tjoi2017]不勤劳的图书管理员 树状数组+分块+二分
- Mybatis 如何自动生成bean dao xml 配置文件 generatorconfig.xml (main()方法自动生成更快捷)
- 使用腾讯互动直播 遇到的坑 &#39;GLIBC_2.14&#39; not found 问题解决
- 标准C程序设计七---30
- ajax 分页(jquery分页插件pagination) 小例1
- css3 nth-child 与 nth-of-type 的区别
- 大话Spark(3)-一图深入理解WordCount程序在Spark中的执行过程