分治NTT:我 卷 我 自 己
2024-10-07 02:29:17
感觉这种东西每次重推一遍怪麻烦的,就写在这里了。
说白了就是根据分治区间左端点是否为\(0\)分类讨论一下,一般是如果不是\(0\)就要乘\(2\),不过还是需要具体问题具体分析一下才好(就比如下面的例子)。
以下面这个东西为例给出代码:
\[f[0]=0,g[0]=0,f[1]=0,g[1]=1
\]
\]
\[f[n]=\sum_{i=0}^{n}\binom{n-2}{i-1}(f[i]f[n-i]+g[i]f[n-i]+g[i]g[n-i])
\]
\]
\[g[n]=\sum_{i=0}^{n}\binom{n-2}{i-1}f[i]g[n-i]
\]
\]
void solve(int l,int r){
if(l==r){
if(l==0)f[l]=g[l]=0;
else if(l==1)f[l]=0,g[l]=1;
else f[l]=1ll*f[l]*fac[l-2]%MOD,g[l]=1ll*g[l]*fac[l-2]%MOD;
return;
}
int mid=((l+r)>>1);solve(l,mid);
m=(mid-l)+(r-l);prepare();
rin(i,0,mid-l)A[i]=1ll*f[l+i]*(l+i==0?0:invf[l+i-1])%MOD,B[i]=1ll*g[l+i]*(l+i==0?0:invf[l+i-1])%MOD;
rin(i,0,r-l)C[i]=1ll*f[i]*(i==0?0:invf[i-1])%MOD,D[i]=1ll*g[i]*(i==0?0:invf[i-1])%MOD;
ntt(A,1);ntt(B,1);ntt(C,1);ntt(D,1);
rin(i,0,n-1){
int temp=A[i];
A[i]=((l==0?1ll:2ll)*A[i]*C[i]+1ll*B[i]*C[i]+(l==0?0ll:1ll)*A[i]*D[i]+(l==0?1ll:2ll)*B[i]*D[i])%MOD;
B[i]=(1ll*B[i]*C[i]+(l==0?0ll:1ll)*temp*D[i])%MOD;
}
ntt(A,-1);ntt(B,-1);
rin(i,mid+1,r)f[i]=(f[i]+A[i-l])%MOD,g[i]=(g[i]+B[i-l])%MOD;
memset(A,0,n<<2);memset(B,0,n<<2);memset(C,0,n<<2);memset(D,0,n<<2);
solve(mid+1,r);
}
最新文章
- http://www.cnblogs.com/kissdodog/p/4159176.html
- JSON帮助类
- maven project中,在main方法上右键Run as Java Application时,提示错误:找不到或无法加载主类XXX.XXXX.XXX
- STM32学习笔记——USART串口
- JS常用方法函数整理
- 理解和使用 JavaScript 中的回调函数
- Mysql新建表,插入中文时报错“Incorrect string value: &#39;\xE4\xBD\xA0\xE5\xA5\xBD&#39; for column”问题
- Excel插件类库的设计思路
- Java学习笔记--Swing2D图形
- bzoj 2049 Cave 洞穴勘测(LCT)
- Java 9 揭秘(18. Streams API 更新)
- 2013 ACM/ICPC Asia Regional Hangzhou Online hdu4739 Zhuge Liang&#39;s Mines
- BZOJ:4873: [Shoi2017]寿司餐厅
- 如何为自己的pip包打造可以执行的系统命令
- Python的内置方法——补充
- Netty ByteBuf 和 String 转换
- Golang 调用 Python 代码
- JaveWeb 公司项目(7)----- 通过JS动态生成DIV
- Java分布式锁的三种实现方案(redis)
- 《Linux内核分析》第二周学习报告