新普金娱乐网址


周末,大家继承坐同桌吧!

【数学】您除了写小说,还在做什么样

数学从今日起做三个甜美的人,戒掉SNS

  • 四月 15, 2019
  • 数学
  • 没有评论

FFT [TPLY]

标题链接
https://www.luogu.org/problemnew/show/1919
https://www.luogu.org/problemnew/show/3803


材质推荐

orz大佬博客
http://www.cnblogs.com/cjoieryl/p/8206721.html (orz YL大佬)
http://blog.csdn.net/iamzky/article/details/22712347 (一级易懂)

知识点
复数:
https://baike.baidu.com/item/%E5%A4%8D%E6%95%B0/254365?fr=aladdin
单位根(单位复数根)
https://baike.baidu.com/item/%E5%8D%95%E4%BD%8D%E6%A0%B9
多项式表示
http://blog.csdn.net/acdreamers/article/details/39005227
卷积
http://blog.csdn.net/bitcarmanlee/article/details/54729807

书本推荐
ACM/ICPC 算法基础练习教程 7.4便捷傅里叶变换
算法导论 30章多项式与敏捷傅里叶变换

觉得看不懂很符合规律,知识点很空洞必要慢慢明白
而对于本文,本文功用为对两位大佬内容解读并且参加本人观点
读者能够先花时间阅读以上推荐的文字,爆发一定知道再读本文.由于小编很弱,或者会爆发错误,还请大神帮衬提出.

从前天起做二个美满的人,戒掉SNS。

自从换了智能机后养成了个习惯,无聊时刷朋友圈、QQ空间、今日头条,刷完事后越发的抽象了。

ifanr: 和对象关系使用最多的工具是什么样?社交软件在您的活着中最首要吗?
对讲机、邮件、及偶尔的 iChat。
自己不用任何 SNS。
自家以为 SNS 的主干是 fo,Instagram这几年最大的贡献之一正是教会了地球人怎么是 fo。不过 fo
的目标是什么吗?更进一步地说,作者最后发现,其实自身最亟需的是两类
fo,1类是 Yammer 式的 fo——作者 fo
的是工作内容。而除了,笔者信任“持续地升级本身”是广大人的人生重心,于是别的一类主要的
fo,正是 Quora 式的 fo 知识。
而关于 Facebook 式和 Facebook 式的 casual
fo,小编想大概本身后天并不须要。笔者曾经结合了还要有了三个要命可爱的姑娘,所以小编不必要再到某些SNS 上通过 casual fo 认识女神了。:)
——————livid

近些年特地注册了V二EX那一个网址,掌握到livid是个11分幽默的人。小编觉着SNS应用推广了人的私欲?比如用来YP。(人不应当学会控制自个儿的欲念吗?就好像控制自身的心态和情绪1样,被本身的欲望所主宰真是可悲啊。)希望团结被点赞,希望本人被关注,渴望别人给本人留言回复等等。

以前,开支了多量的光阴去关注与和睦毫无干系的剧情。哇!高级中学同学去上海了,哇!喜欢的女人去吃东西拍了过多美味的食物照片,等等。自己想在事后自身才应该是人生的重头戏吧。


少上网。中夏族民共和国家足球队队员下的互连网上存在着多量只是为着创业,却并非来自创办人自己内心真实想法的品类。那些类别的留存所追求的,正是何许能够让规模变得越来越大。于是为了能够变大,他们天天钻探并使用人性的毛病。当人性中的弱点真的被她们抓住时,数据会愈发帮扶他们肯定成就感。那是眼下我们的社聚会场地面临的题目——大多数新的被创设出来的东西,并非是以一种
organic
的法子。于是事物本来的自然的发育进程被人为的增长速度和扭转,只要能够发出美观的数量。小编不可能让投机掉入那么些无聊的陷阱。小编更相当的小概去加入生产那样的庸俗。
——————livid《关于灵感的诗歌》

网路上应该是不分男女的啊?可又不是,和讯上四个非凡的爆照就能有几千的关怀,回答二个标题附上张赏心悦目的肖像就会有那些同情。(当然主即使看容颜)笔者认为自个儿早就被SNS下边传出的资源消息洗脑了,在此之前向来没听他们说过“看脸”、“白富美”、“高帅富”。

既往自家相信美好的事物,相信纯粹的情感,相信努力加油是足以达成目的的。不过今后却成了“主要依旧看脸”、“拼爹”、“英雄,来干了那碗鸡汤”。男子被洗脑后得以明日看看位能够的女孩子,今天就去提亲,被拒之后后天就说不再喜欢了。更吓人的业务可能是:当大家被洗脑后本人却全然不知。

Galaxy无名
5 days ago Posts: 0
为了您好,请容作者武断地提议,网路的金子规则之一就是“网路上未有女性”。那条规则的意味和你想的不雷同。现实中,人们爱好您的女性身份。他们想跟你嘿咻,他们关心您,假装对您说的话感兴趣,认为你玲珑幽默。网路上,大家没机会跟你嘿咻,那意味你的”女性“优势未有。你和作者讲讲时,并不会因本身的情欲而取得加分。当您的篇章内冒出”大姐小编……”时,你是在伸手别人注意你。你强调本身是女人只是为着得回女性的优势,因为没了女性优势,你的稿子就只是篇无趣,粗笨,空洞的哔哔。你忘了网路黄金规则:网路上未有女性。规则的唯1分裂,能让你在网路上海重型机器厂10女性优势的两样,正是贴出你本人的露奶照。那对你的话是种侮辱和物化,但在网路上,你唯壹的能让我们对你激起兴趣的唯有你的裸照。
给因为小说太长而无意看的人:不露奶就滚蛋!

看了默默贴话后专门有感触,有句话说过“你永远不领会坐在你电脑对面包车型大巴是一条狗”。在网路上只怕唯有排除了性别因素,一碗水端平了才能很好的沟通思想,调换想法才能最后找到真正的soulmate了啊?(好像在切实中也同等)


原谅本人又想开了个相关的事:网路上心情话题是或不是有些过多了哟?关键词比如:恋爱、妹子、高校、心思什么的。难道那世界就只剩余那个了吧?未有任何越来越好玩的东西了啊?

新浪上每一日有324八二个难题诞生,个中1壹五柒拾4个属于两性子感类。
————天涯论坛答案

要清楚,世界上有十分部分老公,爱情在他们的性命里占的比例并不高。
本身纪念搜狐上业已有个学霸男子,万分认真的回过1个答案,说比起女性来说她率真觉得数学更掀起人。小编可怜通晓他,给她点了赞。
以此世界上幽默的东西、好玩的东西、纠结人的事物、令人着魔的事物实在是太多太多,完全不可能容忍把绝超越八分之四小时放在谈恋爱上的大有人在。而且据自身的洞察,层次越高那样的人就更加多,这一个人再3有总体强烈的本人世界,对外不想花太多精力在人际关系上,个中自然也席卷谈恋爱。
———————今日头条答案

多少东西远比人际关系更令人着魔吧!

正文

自小编要去追寻它。

Part1.初识FFT

职能:求多项式乘法的周密(便是初级中学学的多项式)
FFT多项式乘法与壹般情势有差异

一般多项式乘多项式法则:
多项式与多项式相乘,先用一个多项式的每1项与另3个多项式的每一项相乘,再把所得的积相加。举八个事例由多项式乘多项式法则足以拿走(a+b)(c+d)=a(c+d)+b(c+d)=ac+ad+bc+bd

FFT‘绕圈’法
FFT处理多项式相乘,先从多项式最普通的表明方式–-周全表明方式转化成点值表明格局再进行点值乘法.最后,再将点值乘法的结果转回周全表明方式.
而从-周详表明形式转化成点值表明方式的历程,我们誉为DFT,即离散傅里叶变换.
点值乘法的结果转回全面表明方式的步调,我们誉为离散傅里叶变换的逆运算,也叫插值.

看了这么多文字,相信你有一些晕晕乎乎的,上面是概念解释
1~对于点值表明式作者的知情 :
点值表达格局正是用多少函数上的点的坐标来代表该函数,比如 f(x)=\(x^2\)-x+2={ ( 0 , 2 ) , ( 1 , 2 ) , ( 2 ,
4 ) }
2~点值表明式的计量:
借使大家明天有用点乘表示的多项式
A(x)={(0,1),(1,2),(2,7)}
B(x)={(0,2),(1,2),(2,4)}
[P.S.:点乘表明式能运算的规范是五个点要有一致的x值]
C(x)={(0,2×1),(1,2×2),(2,7×4)}={(0,2),(1,4),(2,28)}

FFT流程图如下:(借鉴旁人博客)
数学 1

part2.复数

0.为何要学习复数?
YL大佬原话:”学习复数,全部这一个7柒八捌的定律,都以为着FFT的奇特变换!”

于是,为了FFT,好好学习复数吧!(再一次ORZ YL大佬)

一.复数的定义:大家把形如a+bi(a,b均为实数)的数称为复数,在那之中a称为实部,b称为虚部,i称为虚数单位,i的值为\(\sqrt{-1}\)
二.单位根的定义:数学上,n次单位根是n次幂为壹的复数。
单位根的概念不理解很健康,上面举个例子(来自百度宏观)
单位的1回根有2个:1
单位的三回根有五个:+一和-一。
单位的三回根是:
{$ 1 $, \(\frac{-1+\sqrt{3}i}{2}\),\(\frac{-1-\sqrt{3}i}{2}\)}
笔者们证雀巢(Beingmate)下
\((\frac{-1+\sqrt{3}i}{2})^3\)=\((\frac{-1+\sqrt{3}i}{2})^2\)×\((\frac{-1+\sqrt{3}i}{2})\)
………………..=\((\frac{1+3i^2-2\sqrt{3}i}{4})\)×\((\frac{-1+\sqrt{3}i}{2})\)
………………..=\((\frac{-2-2\sqrt{3}i}{4})\)×\((\frac{-1+\sqrt{3}i}{2})\)
………………..=\((\frac{(-2)×(1+\sqrt{3}i)×(\sqrt{3}i-1)}{8})\)
………………..=-\((\frac{1}{4})\)×(\(3i^2-1\))
………………..=\(-(\frac{1}{4})\)*(-4)
………………..=1
所以\(\frac{-1+\sqrt{3}i}{2}\)是单位的一回根
单位的八次根是{壹,+i,-壹,-i}

可望您曾经知道了哪些是单位复数根(单位根),我们继续

对于w\(_n\)=\(e^{2πi/n}\)我们称w\(_n\)为n次单位根(前边讲了n次单位跟哦)
(普及一下:复数指数方式的概念:\(e^{iu}\)=cos(u)+isin(u))
上边有1对定律须求牢记(YL大佬的忠告)
PS由于太弱不会注明,网上有许多表明哦
(w上标代表指数)
消去引理
\[\omega^{dk}_{dn}=\omega^{k}_{n}\]
本条引理分外可怜关键哦,你后边必然肯定晤面到!
10分,分外首要!记住!
扣除引理
\[(\omega^{k+\frac{n}{2}}_{n})^{2}=\omega^{2k+n}_{n}=\omega^{2k}_{n}\omega^{n}_{n}=(\omega^{k}_{n})^{2}\]
求和引理
\[\Sigma^{n-1}_{j=0}(\omega^{k}_{n})^{j}=0\]

这么些复杂的数学公式可能会使您以为枯燥无味,但为前面包车型大巴运算奠定了首要的根底,精通一下下啦!

Part3.DFT与-DFT进阶

在本章内于括号里面包车型大巴数为啥是\(\omega^{k}_{n}\)而不是x,你要到FFT才能明白.但本章内容中的\(\omega^{k}_{n}\)你能够当成x看(下1章就卓绝了)

DFT
对于k=0~n-1,定义:
\[y_k=A(\omega^{k}_{n}) =
\Sigma^{n-1}_{j=0} a_j(\omega^{k}_{j})^j\]
对此那么些姿势,你这么看\(y_k=A(x)=\Sigma^{n-1}_{j=0}
a_j(x)^j\)
大家知道DFT求的是点乘
点乘正是坐标(后面忘讲了:坐标的数目肯定要压倒等于n,表明网上有详实表达)
日常你是怎么求坐标的?
选定1个x值,把x值带到个中求出y
上面这些姿势正是那般做的呀(还不懂就再看看多项式的周详表明式)

因此我们继续分析,对于每贰个x,我们都要O(n)地将值带到多项式里求值,我们起码要n个坐标,所以总复杂度是O(n*n)

最终我们将获得的y称为a的离散傅里叶变换,记作\(y=DFT_n(a)\) \((那里的y,a指的是具备的y_k,a_k(k有n种,也正是要取k个))\)

本条概念先记着,还要注意的是,这一步的意义是将全面表明格局变成点乘表明方式O(nn).再用事先的点乘算法算出点乘的结果O(n)(Part一.讲了点乘,复杂度申明很鲜明).最终用上边包车型大巴离散傅里叶逆变换(作者叫它-DFT),再换回去O(nn)所以总复杂度为O(n*n)

-DFT
万分抱歉作者要么不会证,只可以摆出结果\[对于y_k
= \Sigma^{n-1}_{i=0}a_i(x)^i\]
\[有a_k =
\frac{1}{n}\Sigma^{n-1}_{i=0}y_i(x)^i\]
再对比DFT公式
\[y_k = \Sigma^{n-1}_{j=0}
a_j(x)^j\]
能够发现,DFT-DFT的差别极小,基本上只是y,a调换了壹晃罢了(也有两样的…)

Part四 FFT水落石出

追根究底来到了最后,前面全数令人头大的背景知识,都以为了那一章而服务.
于是那1章是任重(英文名:rèn zhòng)而道远的.
一经近日还未曾完全精晓,请重新巩固扎实.

网上都说,FFT的复杂度为O(nlgn)
那是怎么来的吗?
答案是:神奇的分治
先把A(x)这么些多项式拆分成奇数项与偶数项
\[A^{[0]}(x) = a_0 + a_2x + a_4x^2 +
… + a_{n-2}x^{\frac{n}{2} – 1}\]
\[A^{[1]}(x) = a_1 + a_3x + a_5x^2 +
… + a_{n-1}x^{\frac{n}{2} – 1}\]
\[A(x) = A^{[0]}(x^2) + xA^{[1]}(x^2)
\]
本条是正确的,希望读者拿起草稿纸自个儿演算一次
我们把那些多项式拆分成这么子之后
复数闪亮登场
起来用复数的公式了哦
大家不要紧把\(\omega^{k}\)带入到x中去
\[A(\omega^k_n)=A^{[0]}((\omega^k_n)^2) +
\omega^k_n A^{[1]}((\omega^k_n)^2)\]
下一场,通过事先涉嫌过的单位复数根消去引理咱俩得以拿走(说了消去引理卓殊首要)
咱们用消去引理把\((\omega^k_n)^2\)化一下
\((\omega^k_n)^2\)=\(\omega^{2k}_n\)

………….=\(\omega^{\frac{2k}{2}}_{\frac{n}{2}}\)

………….=\(\omega^{k}_{\frac{n}{2}}\)
所以
\[原式=A^{[0]}(\omega^k_{\frac{n}{2}})

  • \omega^k_n A^{[1]}(\omega^k_{\frac{n}{2}}) \]
    又因为\[\omega^{\frac{n}{2}}_{n}=\omega_{2}=e^{k\pi
    i}= cos k\pi + i sin k\pi = -1\]
    所以
    \[A(\omega^{k+\frac{n}{2}}_n)=A^{[0]}(\omega^k_{\frac{n}{2}})
  • \omega^k_n A^{[1]}(\omega^k_{\frac{n}{2}})\]
    这么就从n个变成了\({\frac{n}{2}}\)个,缩了大体上
    聊起底,再观察历次依照奇偶地方分割所形成的树(博主多谢又借转手您的图形)
    数学 2
    咱俩得以窥见每一个数和他二进制相反的职位调换!!(比如,壹与4发生交流)
    从而就能够用迭代的章程了

代码

FFT原理是1次事,代码又是另二遍事,最棒依然把它背下来

总会有用的!

//P3803 【模板】多项式乘法(FFT)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>

#define rg register int
#define ll long long
#define db double
#define il inline

#define INF 2147483647
#define SZ 10000001

using namespace std;

const double pi=acos(-1);

struct Complex
{
    db r,i;
    Complex(){}
    Complex(db a,db b):r(a),i(b) {}
    Complex operator+(const Complex B)const
    {return Complex(r+B.r,i+B.i);}
    Complex operator-(const Complex B)const
    {return Complex(r-B.r,i-B.i);}
    Complex operator*(const Complex B)const
    {return Complex(r*B.r-i*B.i,r*B.i+i*B.r);}
};
Complex X,Y,a[SZ],b[SZ];

int r[SZ],n,m,l;
il void FFT(Complex *a,int x)
{
    for(rg i=0;i<n;++i) if(i<r[i]) swap(a[i],a[r[i]]);
    for(rg i=1;i<n;i<<=1)
    {
        Complex wn(cos(pi/i),x*sin(pi/i));
        for(rg j=0;j<n;j+=(i<<1))
        {
            Complex w(1,0);
            for(rg k=0;k<i;++k,w=w*wn)
            {
                X=a[j+k],Y=a[i+j+k]*w;
                a[j+k]=X+Y,a[i+j+k]=X-Y;
            }
        }
    }
    if(x==-1) for(rg i=0;i<n;++i) a[i].r=a[i].r/n;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(rg i=0;i<=n;++i) scanf("%lf",&a[i].r);
    for(rg i=0;i<=m;++i) scanf("%lf",&b[i].r);
    m+=n;for(n=1;n<=m;n<<=1) ++l;
    for(rg i=0;i<n;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    FFT(a,1);FFT(b,1);
    for(rg i=0;i<=n;++i) a[i]=a[i]*b[i];
    FFT(a,-1);
    for(rg i=0;i<=m;++i) printf("%d ",(int)(a[i].r+0.5));
    return 0;
}

P1919 【模板】A*B Problem升级版(FFT快速傅里叶)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>

#define rg register int
#define ll long long
#define il inline
#define ldb long double

#define INF 2147483647
#define SZ 1000001

using namespace std;
const ldb pi=acos(-1);

struct Complex
{
    ldb r,i;
    Complex(){}
    Complex(ldb a,ldb b):r(a),i(b){}
    il Complex operator+(const Complex B)const
    {return Complex(r+B.r,i+B.i);}
    il Complex operator-(const Complex B)const
    {return Complex(r-B.r,i-B.i);}
    il Complex operator*(const Complex B)const
    {return Complex(r*B.r-i*B.i,r*B.i+i*B.r);}
};
Complex X,Y,a[SZ],b[SZ];
int n,m,l,r[SZ];
il void FFT(Complex *a,int x)
{
    for(rg i=0;i<n;++i) if(i<r[i]) swap(a[i],a[r[i]]);
    for(rg i=1;i<n;i<<=1)
    {
        Complex wn(cos(pi/i),x*sin(pi/i));
        for(rg j=0;j<n;j+=(i<<1))
        {
            Complex w(1,0);
            for(rg k=0;k<i;++k,w=w*wn)
            {
                X=a[j+k],Y=a[i+j+k]*w;
                a[j+k]=X+Y,a[i+j+k]=X-Y;
            }
        }
    }
    if(x==-1) for(rg i=0;i<n;++i) a[i].r=a[i].r/n;
}

char ch1[SZ],ch2[SZ];
int res[SZ];
int main()
{
    scanf("%d",&n);
    cin>>ch1;
    cin>>ch2;
    for(rg i=0;i<n;++i)
    {
        a[i].r=ch1[n-i-1]-'0';
        b[i].r=ch2[n-i-1]-'0';
    }
    m=n+n-2;for(n=1;n<=m;n<<=1) ++l;
    for(rg i=0;i<n;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    FFT(a,1);FFT(b,1);
    for(rg i=0;i<=n;++i) a[i]=a[i]*b[i];
    FFT(a,-1);
    for(rg i=0;i<=m;++i) res[i]=(int)(a[i].r+0.5);
    for(rg i=0;i<=m;++i) res[i+1]+=res[i]/10,res[i]%=10;
    rg top=m+1;
    while(res[top]>9)
    {
        res[top+1]=res[top]/10;
        res[top]%=10;
        ++top;
    }
    while(!res[top]) --top;
    for(rg i=top;i>=0;--i)
     printf("%d",res[i]);
    return 0;
}

几点注意
pi 最棒不用手写(当然假诺你能背到小数点后1玖位小编也不栏你)
否则很或者出精度难题
最权威写Complex速度快很多
只顾一些从0起始的地点
加油哦!

END

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图