标签 fft 下的文章:

3456: 城市规划 CDQ分治+NTT 计数问题
发表于: | 分类:Oi | 评论:0 | 阅读:153
求$n$个点无向连通图的方案数 首先我们非常容易得到一个$n^2$的递推式,设$f(i)$表示$i$个点无向连通图的方案数,那么我们用所有情况的方案数减去不合法的方案数,不合法的话我们可以枚举$1$所在的联通块的大小进行计算,用$t(x)$表示$x$个点形成的完全...

阅读全文>>

BZOJ 4624: 农场种植 FFT 构造匹配问题
发表于: | 分类:Oi | 评论:0 | 阅读:116
我们可以把两个串都展成一维的,然后枚举起点的时候注意合法就行了,注意第二个串要展成和第一个串一样长 然后把两个串中的H换成1,'G'换成-1,然后第二个串剩下的都是0补位就行了 最后把第二个串翻转一下然后大力乘在一起就行了,注意到相同的贡献是1,不同的贡献是-1,...

阅读全文>>

BZOJ 4836: [Lydsy2017年4月月赛]二元运算 分治+FFT
发表于: | 分类:Oi | 评论:0 | 阅读:129
套路题…… 考虑如果只是计算$x+y$的影响我们把生成函数乘一下就行了 如果只是计算$x-y$的影响我们把第二个生成函数指数都置成相反数然后乘一下就行了 现在对于不同的$x,y$关系计算方式不用怎么办? 大力分治就行了,$solve(L,R)$表示处理值域在$(L...

阅读全文>>

BZOJ 4827: [Hnoi2017]礼物 FFT 数学
发表于: | 分类:Oi | 评论:0 | 阅读:112
遇到式子我们就展开一下吧 $\sum{(x_i-y_i)^2 } = \sum{x_i^2} +\sum{y_i^2}-2\sum{x_i*y_i}$ 发现了一个多项式乘法,然后我们按照经验把 $y$ 数组翻转一下 $\sum{x_i^2} +\sum{y_{n-...

阅读全文>>

HDU5730 cdq+FFT
发表于: | 分类:Oi | 评论:0 | 阅读:110
题目大意 给出长度分别为$1~n$的珠子,长度为$i$的珠子有$a_i$种,每种珠子有无限个,问用这些珠子串成长度为$n$的链有多少种方案 大概这个东西就是强行套了一波两个模板233333首先容易得到$$f(i)=\sum\limits_{j=0}^{i-1...

阅读全文>>

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP