最近做大爷们出的训练题，基本每天一道FFT...但是似乎我对FFT的理解只停留在“可以求两个数组的卷积”+背代码阶段，感觉再不重新学一遍要跟不上时代的脚步了...
[12.7]差不多就到这儿吧。。感觉把教材pyx的博客上的每一块都看了一遍，但是感觉做题还是不大会用。。如果以后闲着无聊想自虐的话可能会去写一下策爷的[tex]e^{A_{(z)}}[/tex]。。（不过我感觉以我的智商估计是写不出来了）
1.首先是最基本的FFT：
重新看了一遍算法导论，感觉也不是特别难理解，果然当初学的时候还是太naive了
【BZOJ2194】FFT快速傅立叶
【BZOJ2179】快速傅立叶之二
void fft(atom *x,int n,int fl=1){
for (int i=(n>>1),j=1;j<n;j++){
if (i<j) swap(x[i],x[j]);
int k;
for (k=(n>>1);i&k;i^=k,k>>=1); i^=k;
}
for (int m=2;m<=n;m=(m<<1)){
atom w=(atom){cos(pi*2*fl/m),sin(pi*2*fl/m)};
for (int i=0;i<n;i+=m){
atom cur=(atom){1,0};
for (int j=i;j<i+(m>>1);j++){
atom u=x[j],v=x[j+(m>>1)]*cur;
x[j]=u+v; x[j+(m>>1)]=u-v; cur=cur*w;
}
}
}
}
2.FNT
想起来感觉还是挺显然的，在模意义下用模意义下的单位根替换。
【某模拟题T1】循环计数 mx爷的题，求斯特林数。把斯特林数的那个式子用分治FNT搞就好了（我偷懒空间是[tex]O(n \log n)[/tex]的，稍微改一改就可以做到[tex]O(n)[/tex]
void fft(int *x,int n,int fl=1){
for (int i=(n>>1),j=1;j<n;j++){
if (i<j) swap(x[i],x[j]);
int k;
for (k=(n>>1);k&i;i^=k,k>>=1); i^=k;
}
int now=0;
for (int m=2;m<=n;m<<=1){
int w; now++; if (fl>0) w=G[now]; else w=nG[now];
for (int i=0;i<n;i+=m){
int cur=1;
for (int j=i;j<i+(m>>1);j++){
int u=x[j],v=1ll*x[j+(m>>1)]*cur%mo;
x[j]=(u+v)%mo; x[j+(m>>1)]=(u-v+mo)%mo;
cur=1ll*cur*w%mo;
}
}
}
}
atom solve(int l,int r){
if (l==r){
C[++tot]=l; C[++tot]=1; return (atom){tot-1,tot};
}
int mid=(l+r)>>1; atom k1=solve(l,mid),k2=solve(mid+1,r);
int n=max(mid-l+1,r-mid),len=1;
while ((1<<len)<=(n<<1)) len++;
for (int i=0;i<(1<<len);i++){A[i]=0; B[i]=0;}
for (int i=k1.l;i<=k1.r;i++)A[i-k1.l]=C[i];
for (int i=k2.l;i<=k2.r;i++)B[i-k2.l]=C[i];
fft(A,1<<len); fft(B,1<<len);
for (int i=0;i<(1<<len);i++) A[i]=1ll*A[i]*B[i]%mo;
fft(A,1<<len,-1);
for (int i=0;i<(1<<len);i++) A[i]=1ll*A[i]*two[len]%mo;
atom ans; ans.l=tot+1;
for (int i=0;i<=r-l+1;i++) C[++tot]=A[i]; ans.r=tot;
return ans;
}
3.分治FFT
利用CDQ分治的思想，FFT可以求解形如[tex]f_n=\sum_{i=1}^{n-1}f_i \times A_{n-i}[/tex]的递推式。
【BZOJ3456】城市规划 可以得到递推式[tex]f_n=2^{\binom{n}{2}}- \sum_{i=1}^{n-1}2^{\binom{n-i}{2}} \times \binom{n-1}{i-1} \times f_i[/tex]，意义就是用所有图减去不连通的图的数量，强制1在一个联通块中枚举这个块的大小。之后转化成卷积的形式就可以分治FFT了。
void fft(int *x,int n,int fl=1){
for (int i=(n>>1),j=1;j<n;j++){
if (i<j) swap(x[i],x[j]);
int k;
for (k=(n>>1);k&i;i^=k,k>>=1); i^=k;
}
int now=0;
for (int m=2;m<=n;m<<=1){
int w; now++; if (fl==1) w=G[now]; else w=nG[now];
for (int i=0;i<n;i+=m){
int cur=1;
for (int j=i;j<i+(m>>1);j++){
int u=x[j],v=1ll*x[j+(m>>1)]*cur%mo;
x[j]=(u+v)%mo; x[j+(m>>1)]=(u-v+mo)%mo;
cur=1ll*cur*w%mo;
}
}
}
}
void solve(int l,int r){
if (l==r){
f[l]=(T[l]-1ll*I[l-1]*f[l]%mo+mo)%mo; return;
}
int mid=l+r>>1; solve(l,mid);
int n=max(mid-l+1,r-mid),len=1;
while ((1<<len)<=(n<<1)) len++;
for (int i=0;i<(1<<len);i++){A[i]=0; B[i]=0;}
for (int i=l;i<=mid;i++)A[i-l]=1ll*nI[i-1]*f[i]%mo;
for (int i=1;i<=r-l;i++)B[i]=1ll*T[i]*nI[i]%mo;
fft(A,1<<len); fft(B,1<<len);
for (int i=0;i<(1<<len);i++) A[i]=1ll*A[i]*B[i]%mo;
fft(A,1<<len,-1);
for (int i=mid+1;i<=r;i++) f[i]=(f[i]+1ll*A[i-l]*two[len])%mo;
solve(mid+1,r);
}
4.多项式求逆
看了pyx的博客（感觉pyx的博客已经可以成为中国多项式从入门到提高到进阶三合一通用教材了）后感觉其实如果想到了倍增的话剩下的还是不怎么难想的。。不过似乎这个模型比较奇怪？感觉转化起来有点费劲。似乎满足[tex]f_n=C_{n}-\sum_{i=1}^{n-1}f_i \times A_{n-i} \times B_{n}[/tex]，如果[tex]B_n[/tex]可以把[tex]f_n[/tex]形式转化为[tex]A_{n-i}[/tex]相同的话就可以用这个了。
【BZOJ3456】城市规划
可以得到[tex] \sum_{i=1}^n 2^{\binom{n-i}{2}} \times (n-i)!^{-1} \times (i-1)!^{-1} \times f_i = 2^{\binom{n}{2}} \times (n-1)!^{-1}[/tex]，然后左边可以看成卷积，就可以把一个多项式除过去（就是乘上逆元）。
一直听别人说这玩意常数巨大，跑得还没有分治FFT快。。实际写了一下速度还是快了那么一点点的，但是复杂度的优势完全没了。
void fft(int *x,int n,int fl=1){
for (int i=(n>>1),j=1;j<n;j++){
if (i<j) swap(x[i],x[j]);
int k;
for (k=(n>>1);i&k;i^=k,k>>=1); i^=k;
}
int now=0;
for (int m=2;m<=n;m<<=1){
int w; now++; if (fl==1) w=G[now]; else w=nG[now];
for (int i=0;i<n;i+=m){
int cur=1;
for (int j=i;j<i+(m>>1);j++){
int u=x[j],v=1ll*x[j+(m>>1)]*cur%mo;
x[j]=(u+v)%mo; x[j+(m>>1)]=(u-v+mo)%mo;
cur=1ll*cur*w%mo;
}
}
}
}
void getrev(int n){
if (n==1){
A[0]=quick(C[0],mo-2); return;
}
getrev((n+1)/2); int len=1;
while ((1<<len)<=((n+1)<<1)) len++;
for (int i=0;i<n;i++) B[i]=C[i]; for (int i=n;i<(1<<len);i++) B[i]=0;
fft(A,1<<len); fft(B,1<<len);
for (int i=0;i<(1<<len);i++) B[i]=(2-1ll*A[i]*B[i]%mo+mo)%mo;
for (int i=0;i<(1<<len);i++) A[i]=1ll*A[i]*B[i]%mo;
fft(A,1<<len,-1);
for (int i=0;i<n;i++) A[i]=1ll*A[i]*two[len]%mo;
for (int i=n;i<(1<<len);i++) A[i]=0;
}
5.多项式除法
依然是pyx的博客...关键就是把多项式reverse，后面的就挺好推了。
练习嘛写了一个多项式多点求值愉♂悦一下，写出来之后妈呀怎么10W10W要跑10S..实在是被慢哭了。（策爷：这种常数巨大的东西没前途了
6.多项式开根
仍旧是pyx的博客。。依然是倍增的思想，考虑平方后把式子转化为[tex]A_{(x)}^2 \equiv B_{(x)}(\text{mod}\ x^{n})[/tex]的形式就好了，还是挺好推的。
【codeforces 250E】小朋友和二叉树
接一个方程可以得到母函数的式子是[tex]F_{(x)}=\frac{2}{1+ \sqrt{1-4A_{(x)}}}[/tex]，其中[tex]A_{(x)}[/tex]是那个集合中的数组成的函数。然后就用多项式开根加求逆算出来[tex]F_{(x)}[/tex]就好了。
void fft(int *x,int n,int fl=1){
for (int i=(n>>1),j=1;j<n;j++){
if (i<j) swap(x[i],x[j]);
int k;
for (k=(n>>1);i&k;i^=k,k>>=1); i^=k;
}
int now=0;
for (int m=2;m<=n;m<<=1){
int w; now++; if (fl==1) w=G[now]; else w=nG[now];
for (int i=0;i<n;i+=m){
int cur=1;
for (int j=i;j<i+(m>>1);j++){
int u=x[j],v=1ll*x[j+(m>>1)]*cur%mo;
x[j]=(u+v)%mo; x[j+(m>>1)]=(u-v+mo)%mo;
cur=1ll*cur*w%mo;
}
}
}
}
void getrev(int n){
if (n==1){
rev[0]=quick(fir[0],mo-2); return;
}
getrev((n+1)>>1); int len=1;
while ((1<<len)<=(n<<1)) len++;
for (int i=((n+1)>>1);i<(1<<len);i++) rev[i]=0;
for (int i=0;i<n;i++) A[i]=fir[i];
for (int i=n;i<(1<<len);i++) A[i]=0;
fft(rev,1<<len); fft(A,1<<len);
for (int i=0;i<(1<<len);i++) A[i]=(2-1ll*A[i]*rev[i]%mo+mo)%mo;
for (int i=0;i<(1<<len);i++) rev[i]=1ll*rev[i]*A[i]%mo;
fft(rev,1<<len,-1);
for (int i=0;i<n;i++) rev[i]=1ll*rev[i]*two[len]%mo;
for (int i=n;i<(1<<len);i++) rev[i]=0;
}
void getroot(int n){
if (n==1){
root[0]=1; return;
}
getroot((n+1)>>1); int len=1,m=((n+1)>>1),n2=two[1];
while ((1<<len)<=(n<<1)) len++;
for (int i=0;i<(1<<len);i++){rev[i]=0; fir[i]=0;}
for (int i=0;i<m;i++) fir[i]=root[i];
getrev(n);
for (int i=0;i<(1<<len);i++) A[i]=0;
for (int i=0;i<n;i++) A[i]=C[i];
fft(fir,1<<len); fft(A,1<<len); fft(rev,1<<len);
for (int i=0;i<(1<<len);i++) A[i]=(1ll*fir[i]*n2%mo+1ll*A[i]*rev[i]%mo*n2%mo)%mo;
fft(A,1<<len,-1);
for (int i=0;i<n;i++) root[i]=1ll*A[i]*two[len]%mo;
for (int i=n;i<(1<<len);i++) root[i]=0;
}
2022年5月22日 00:35
Great stuff. i am going to bookmark it, if you are looking for lyca beltegoed, lebara beltegoed, lyca bundel xs, samsung a52, samsung a51, samsung a72, iphone 13 pro max in Netherlands, get in touch with us.
2022年8月10日 00:07
DNS Port which is abbreviated as Domain Name System is used to configure and sync the Domain name from a Domain service provide to an IP Address of a hosting. In order for a website to be hosted on the Internet and to function smoothly, there should be fixed DNS and it translates the required information to the hosting, so the worldwide web can access the service as well. what is a DNS Server In simple terms, we can consider a Domain name and let us take the example of Google.com and here the Google.com is called the website full name, where the Google is only the partial domain name representing the main keyword.
2022年12月28日 15:17
敬启者：个人小网站希望大家多多支持 感谢您对我们热心的支持（自己人啊） f88tw┃华歌尔┃I appreciate your kind assistance.
https://mypaper.pchome.com.tw/f88tw
f88tw|修坟|修墓|新竹|桃园|苗栗|捡骨|拾骨|发票
https://mypaper.pchome.com.tw/f88tw/post/1370781143
https://mypaper.m.pchome.com.tw/f88tw/post/1370781143
2023年1月08日 02:22
Hello, I think your site might be having browser compatibility issues. When I look at your website in Safari, it looks fine but when opening in Internet Explorer, it has some overlapping. I just wanted to give you a quick heads up! Other then that, very good blog!
2023年4月23日 00:38
crediblebh
2023年5月08日 21:43
I would like to thnkx for the efforts you have put in writing this site. I’m hoping the same high-grade site post from you in the upcoming as well. In fact your creative writing abilities has inspired me to get my own site now. Really the blogging is spreading its wings fast. Your write up is a great example of it. rentacarkosovo Andrew Tate Quotes
2023年5月09日 19:35
Youre so cool! I dont suppose Ive read something like this before. So nice to find somebody with some original thoughts on this subject. realy thank you for beginning this up. this web site is one thing that’s needed on the web, somebody with a bit of originality. helpful job for bringing one thing new to the internet! slot gacor
============
Lots of people were enthusiastic players or enjoyed music and dancing. You may recall that you were most joyful on the performing track. Nonetheless, with increasing accountabilities you may have found almost no time to have pleasure in any of your interests. Are you affected by depression and want to get out of its abysmal depths without lifelong antidepresants? You could attempt and feel free to overcome depression the natural way. flum
2023年5月10日 04:17
I obtained in this article coming from The search engines. This kind of appears a great posting. As i comprehensively appreciated browsing your web blog, i could be likely to go back. That i stored yuor web blog i in addition passedyour can i a few close relatives in the process. I hope you don’t imagination! Daman lotto -=-============= I am only writing to let you understand what a really good discovery my girl encountered browsing your site. She noticed several things, which include what it is like to have an awesome helping mindset to make the rest just know just exactly specific specialized subject areas. You truly surpassed people’s desires. Thank you for rendering these priceless, dependable, revealing and easy guidance on that topic to Janet. tech Gadgets
2023年5月11日 19:31
I randomly browse blogs on the internet, and that i discover your article to be very informational. I have already bookmark it on my browser, in order that I can read your blog publish once more later. Additionally, i am wondering whether or not or not your weblog is open for link exchange, as i actually need to trade links with you. I don’t normally do that, but I hope that we are going to have a mutual hyperlink exchange. Let me know and have an ideal day! beaver creek shuttle from denver
2023年5月11日 22:30
Some really choice content on this internet site . globalcashpartners.com
2023年5月13日 00:14
Needed to compose you a tiny note to finally thank you very much yet again for your personal splendid methods you have discussed above. It is strangely open-handed with people like you to provide publicly all that a number of people would have marketed as an electronic book to generate some bucks for their own end, primarily now that you could possibly have tried it if you ever wanted. These inspiring ideas likewise acted like a fantastic way to know that the rest have the same dreams really like my personal own to see a whole lot more concerning this problem. I’m sure there are thousands of more enjoyable times in the future for many who check out your blog. Dextools Hot List
============
never saw a website like this, relaly impressed. compared to other blogs with this article this was definatly the best site. will save. Fast Track CMC
2023年5月13日 03:19
Just wanted to let you know that I enjoy reading your posts. Don’t have much to add, cheers! สมัคร บาคาร่า ออนไลน์
============
i signed up on clicksor last month and i was impressed with the amount of money i made in one month` Ketamine powder online shop
2023年5月14日 08:49
I simply could not go away your site prior to suggesting that I actually enjoyed the standard information an individual supply to your visitors? Is gonna be again continuously in order to check out new posts cipit88
==========
pay per click programs are really great, i could earn some decent cash from it.. alibabaslot
2023年5月14日 23:58
It¡¦s actually a great and useful piece of information. I am happy that you shared this helpful information with us. Please keep us informed like this. Thanks for sharing. Canon Support Canada
2023年5月15日 05:33
This really is an incredibly amazing powerful resource that you’re offering and you just provide it away cost-free!! I comparable to discovering websites that view the particular price of providing you beautiful learning resource for zero cost. We truly dearly loved examining this web site. Be thankful! skg
=================
Aw, this became an extremely good post. In thought I have to invest writing like this additionally – taking time and actual effort to make a good article… but what can I say… I procrastinate alot and no indicates manage to go done. 3king
2023年5月16日 03:56
general blogging is great because you can cover a lot of topics in just a single blog,, Trouser for mens in pakistan
2023年5月16日 19:43
After study many of the websites for your website now, and I genuinely much like your technique for blogging. I bookmarked it to my bookmark website list and you will be checking back soon. Pls consider my web site likewise and let me know what you consider. ALPILEAN
2023年5月16日 21:38
When I originally commented I clicked the -Notify me when new surveys are added- checkbox and after this each time a comment is added I am four emails sticking with the same comment. Could there be that is it is possible to eliminate me from that service? Thanks! id master internasional ============= I must point out my appreciation for your generosity supporting women who absolutely need help with this question. Your special commitment to passing the solution throughout was remarkably functional and has continually helped associates just like me to attain their ambitions. Your amazing warm and helpful suggestions signifies this much to me and especially to my colleagues. Best wishes; from everyone of us. 제주도여성전용마사지
2023年5月16日 21:47
hey there and thank you for your information – I’ve certainly picked up anything new from right here. I did however expertise some technical points using this site, as I experienced to reload the web site lots of times previous to I could get it to load properly. I had been wondering if your web hosting is OK? Not that I am complaining, but slow loading instances times will very frequently affect your placement in google and could damage your high-quality score if advertising and marketing with Adwords. Anyway I am adding this RSS to my email and could look out for much more of your respective intriguing content. Ensure that you update this again soon.. https://metalshout.com
2023年5月16日 23:12
I would really love to guest post on your blog. Top Delaware Business Startup Formation Lawyer --------------- Wanted to say this blog is quite good. I always want to hear something totally new about this because We have the same blog in my Country about this subject so this help´s me a lot. I did looking about the issue and located a large amount of blogs but nothing beats this. Thanks for sharing so much inside your blog.. SEO Manchester
2023年5月16日 23:18
A powerful share, I simply given this onto a colleague who was doing a bit of analysis on this. And he the truth is purchased me breakfast as a result of I found it for him.. smile. So let me reword that: Thnx for the treat! However yeah Thnkx for spending the time to debate this, I really feel strongly about it and love reading more on this topic. If potential, as you change into expertise, would you mind updating your weblog with more particulars? It’s extremely useful for me. Big thumb up for this weblog post! Cardano
==============
That is the fitting weblog for anyone who needs to find out about this topic. You understand a lot its virtually exhausting to argue with you (not that I really would want…HaHa). You undoubtedly put a brand new spin on a subject thats been written about for years. Nice stuff, just great! Golf Cart Rentals
2023年5月17日 08:12
Hello there, I found your site via Google while looking for a comparable matter, your website came up, it seems to be great. I have bookmarked it in my google bookmarks. Kattenhalsband met naam en belletje
2023年5月17日 18:49
Some truly interesting information, well written and broadly user pleasant. vlc
2023年5月17日 18:49
Very Nice website. I recently designed mine and that i was yearning for some concepts and you gave me a couple of. may i ask you whether you developed the website by youself ? kurulus osman season 3 episode 5
2023年5月18日 03:06
bike racks could really help you secure your bike when you leave it ~ commercial kitchen repair service near me
2023年5月18日 05:25
Hi there, I found your website via Google while searching for a related topic, your website came up, it looks great. I have bookmarked it in my google bookmarks. plombier bruxelles
2023年5月19日 00:16
Hey dude, what kind of wordpress theme are you using? i want it to use on my blog too “ kako sam pobijedila anksioznost
=============
wonderful post, very informative. I wonder why the other experts of this sector do not notice this. You should continue your writing. I’m confident, you have a great readers’ base already! wedding planners in los angeles
2023年5月19日 05:08
Hey there! This post couldn’t be written any better! Reading this post reminds me of my old room mate! He always kept chatting about this. I will forward check this blog
==========
Great post! I?m just starting out in community management/marketing media and trying to learn how to do it well – resources like this article are incredibly helpful. As our company is based in the US, it?s all a bit new to us. The example above is something that I worry about as well, how to show your own genuine enthusiasm and share the fact that your product is useful in that case เว็บยูฟ่า
2023年5月19日 22:00
I read that Post and got it fine and informative.
2023年5月20日 04:06
Heya this is a good post. I’m going to e-mail this to my friends. I came on this while exploring on bing I’ll be sure to come back. thanks for sharing. دردشة عربية
2023年5月21日 01:34
Awesome! I appreciate your contribution to this matter. It has been useful. my blog: how to finger a girl Situs Judi Slot
2023年5月23日 01:25
When visiting blogs, i always look for a very nice content like yours “ เว็บแทงบอล
2023年5月24日 00:42
Youre so cool! I dont suppose Ive read anything like this prior to. So nice to locate somebody with original thoughts on this subject. realy we appreciate you beginning this up. this amazing site is a thing that is required on the web, a person with a little originality. beneficial purpose of bringing interesting things to your internet! สล็อตเว็บตรง ฝากผ่านวอเลท เครดิตฟรี
2023年6月01日 08:15
Thinking of consistently foreclosures in florida on the agenda limited if it is bill-paying time? Will them appear to be any take-home pay shrinks plus every single payment evolves astronomically? dry cleaners near me