[快速变换专题][FFT/NTT/MTT/FWT]Duliu多项式学习笔记
\(Tips:\)本文数学公式较多(可能我写的烂),加载较慢耐心等待,如有[Math Process Error]
的情况请刷新。
该来的还是要来qwq
现在的题真Duliu,\(10\)道题\(9\)个是\(FFT/NTT\),还有一个\(FWT\)。
最近做题遇到一堆要优化到\(nlog_2n\),没办法只能学了。。
写一篇 自己都看不懂的 \(blog\)加深理解
\(Easy-1.FFT\)
定义
FFT\((Fast\ Fourier\ Transformation)\)
中文名称:快速傅里叶离散变换
(Fake Funny TLE)
\(Q:\)这个东西是用来干什么的呢?
\(A:\)想必大家都知道\(FFT\)可以快速求高精乘法吧。
利用\(FFT\)可以做到在\(O(nlog_2n)\)的复杂度内快速求出两个多项式/卷积相乘的结果
多项式
对于一个形如
\[A(x)=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\dots+a_0x^0=\sum_{i=0}^{n-1}a_ix^i\]
的式子,称其为一个多项式。其中最大的次数称为多项式的次数。
系数表示
将\(n-1\)次多项式的系数看做一个\(n\)维向量:
\[\vec a=(a_0,a_1,\dots,a_{n-1})\]
即为多项式的系数表示
点值表示
对于一个\(n-1\)次多项式\(A(x)\),将\(n\)的不相同的\(x\)代入得到一系列点\(\{(x_0,y_0)\dots\}\),可以唯一确定多项式\(A(x)\)
多项式乘法
对于两个多项式\(A(x),B(x)\)
\[A(x)=\sum_{i=0}^{n-1}a_ix^i,B(x)=\sum_{i=0}^{n-1}b_ix^i\]
有\(C(x)=A(x)* B(x)\)
\[C(x)=\sum_{i=0}^{2n-2}\sum_{j+k=i}a_jb_kx^i\]
卷积
对于两个向量\(\vec a=(a_0,a_1,\dots,a_{n-1}),\vec b=(b_0,b_1,\dots,b_{n-1})\)
有卷积\(\vec a\otimes\vec b=c(c_0,c_1,\dots,c_{2n-2})\)
其中有\(c_k=\sum_{i,j}^{i+j=k}\limits a_ib_j\)
和上面多项式乘法非常类似。
那么如何计算多项式乘法呢?
一个显然的做法是按照定义\(O(n^2)\)计算。
不过我们发现,对于两个点值表示\(\{(ax_0,ay_0),\dots\},\{(bx_0,by_0),\dots\}\),可以\(O(n)\)地相乘得到\(C(x)\)的点值表达式。
那么有没有什么方法可以快速的将多项式转成点值表示和逆回来呢?
有的有的,请留下您的邮箱 \(FFT\)就可以做到这一点。
\(FFT\)大概包含\(3\)个步骤:
Part1
多项式 \(\Rightarrow\) 点值表示 (\(DFT,O(nlog_2n)\))
Part2
点值表示相乘 (\(O(n)\))
Part3
点值表示 \(\Rightarrow\) 多项式 (\(IDFT,O(nlog_2n)\))
Prepare
复数
复数由实部和虚部组成,例如\(2+3i\)(其中\(i\)为虚数单位,\(i^2=\sqrt{-1}\))。可以把它理解为一个点或向量\((2,3)\)。
复数运算法则:
加法
实部虚部分别相加
\((2+3i)+(3+3i)=(5+6i)\)
乘法
类似多项式乘法,在坐标系中直观表现为模长相乘,幅角相加(幅角为\(x\)轴逆时针转动的角度)。
\((2+3i)* (3+3i)=6+6i+9i+9i^2=(-3+15i)\)
除法
类似分数的化简
\(\frac{2+3i}{3+3i}=\frac{(2+3i)* (3-3i)}{(3+3i)* (3-3i)}=\frac{6-6i+9i-9i^2}{9-9i^2}=\frac{15+3i}{18}=\frac{15}{18}+\frac{3i}{18}\)
图就不画了,
太麻烦了。
思想
规定点值表示中的\(n\)个\(x\)值为\(n\)个模长为\(1\)的复数。
但是并不是随机的复数,是均匀分布在单位圆(以原点为圆心,半径为\(1\))上的\(n\)个复数,将圆\(n\)等分。
将点从\(0\)开始标号,设第\(0\)个点为\(\omega_n^0\)(和我一起读,\(Omega\sim\)),以此类推。
以\((1,0)\)为起点,由复数乘法规则得:\(\omega_n^i\)的模长一定是\(1\)。
则\(\omega_n^i\)对应的点为\((\cos(\frac{i}{n}2\pi),\sin(\frac{i}{n}2\pi))\)。(采用弧度制)
把这些复数称为\(n\)次单位根。
接下来进入正题。
DFT (Discrete Fourier Transform)
\(Q:\)学了这么多,但是复杂度不还是\(O(n^2)\)吗?
\(A:\)下面就介绍\(O(nlog_2n)\)的算法。
\(Cooley-Tukey\)算法
发明者:\(J.\ W.\ Cooley\&J.\ W.\ Tukey\)
思想:分治
使\(n=2^m(m\in \mathbb{Z})\),若不够高位用\(0\)补齐(显然没有影响)。
接着,对于多项式\(A(x)=\sum_{i=0}^{n-1}\limits a_ix^i\),将其各项按次数奇偶性分类:
\[A(x)=(a_0x^0+a_2x^2+\dots+a_{n-2}x^{n-2})+(a_1x^1+a_3x^3+\dots+a_{n-1}x^{n-1})\]
现在设:
\[A_1(x)=(a_0x^0+a_2x^1+\dots+a_{n-2}x^{\frac{n-2}2})\]
\[A_2(x)=(a_1x^0+a_3x^1+\dots+a_{n-1}x^{\frac{n-2}2})\]
则有:
\[A(x)=A_1(x^2)+xA_2(x^2)\]
对于\(k<\frac n2,\)有:
\[A(\omega_n^k)=A_1(\omega_n^{2k})+\omega_n^kA_2(\omega_n^{2k})\]
\[=A_1(\omega_{\frac n2}^k)+\omega_n^kA_2(\omega_{\frac n2}^k)\]
同理,对于\(k+\frac n2\)有:
\[A(\omega_n^{k+\frac n2})=A_1(\omega_n^{2k+n})+\omega_n^{k+\frac n2}A_2(\omega_n^{2k+n})\]
\[=A_1(\omega_{\frac n2}^k*\omega_n^n)+\omega_n^k*\omega_n^{\frac n2}A_2(\omega_{\frac n2}^k*\omega_n^n)\]
因为\(\omega_n^{\frac n2},\omega_n^n\) 分别对于着\((-1,0),(1,0)\),则
\[A(\omega_n^{k+\frac n2})=A_1(\omega_{\frac n2}^k)-\omega_n^kA_2(\omega_{\frac n2}^k)\]
于是,问题被分成了更小的子问题,递归求解即可。
时间复杂度?这不某年初赛题吗 \(T(n)=2T(\frac n2)+O(n)=O(nlog_2n)\)
IDFT (Inverse Discrete Fourier Transform)
\(Q:\)既然把多项式变成了点值表示,那么怎么把它变回去呢??
首先,这个问题相当于解一个线性方程组:
\[\begin{cases}a_0(\omega_n^0)^0\quad+a_1(\omega_n^0)^1\quad+\cdots+a_{n-1}(\omega_n^0)^{n-1}\quad=A(\omega_n^0)\\a_0(\omega_n^1)^0\quad+a_1(\omega_n^1)^1\quad+\cdots+a_{n-1}(\omega_n^1)^{n-1}\quad=A(\omega_n^1)\\\qquad\vdots\qquad\qquad\vdots\qquad\qquad\ddots\qquad\qquad\vdots\qquad\qquad\qquad\vdots\\a_0(\omega_n^{n-1})^0+a_1(\omega_n^{n-1})^1+\cdots+a_{n-1}(\omega_n^{n-1})^{n-1}=A(\omega_n^{n-1})\end{cases}\]
写成矩阵:
\[\begin{bmatrix}(\omega_n^0)^0&(\omega_n^0)^1&\cdots&(\omega_n^0)^{n-1}\\(\omega_n^1)^0&(\omega_n^1)^1&\cdots&(\omega_n^1)^{n-1}\\\vdots&\vdots&\ddots&\vdots\\(\omega_n^{n-1})^0&(\omega_n^{n-1})^1&\cdots&(\omega_n^{n-1})\end{bmatrix}\begin{bmatrix}a_0\\a_1\\\vdots\\a_{n-1}\end{bmatrix}=\begin{bmatrix}A(\omega_n^0)\\A(\omega_n^1)\\\vdots \\A(\omega_n^{n-1})\\\end{bmatrix}\]
求解矩阵逆我会,高斯消元
\(O(n^3)\)是不可能的,这辈子都不可能的。
设上面式子中左边矩阵为\(X\)
现在考虑矩阵\(Y,Y_{i,j}=(\omega_n^{-i})^j,Z=X* Y\)
则:
\[Y=\begin{bmatrix}(\omega_n^{-0})^0&(\omega_n^{-0})^1&\cdots&(\omega_n^{-0})^{n-1}\\(\omega_n^{-1})^0&(\omega_n^{-1})^1&\cdots&(\omega_n^{-1})^{n-1}\\\vdots&\vdots&\ddots&\vdots\\(\omega_n^{-(n-1)})^0&(\omega_n^{-(n-1)})^1&\cdots&(\omega_n^{-(n-1)})\end{bmatrix}\]
\[Z_{i,j}=\sum_{k=0}^{n-1}X_{i,k}Y_{k,j}\]
\[=\sum_{k=0}^{n-1}\omega_n^{ik}\omega_n^{-jk}\]
\[=\sum_{k=0}^{n-1}\omega_n^{k(j-i)}\]
那么当\(i=j\)时
\[Z_{i,j}=n\omega_n^0=n\]
否则当\(i\not=j\)时
由等比数列求和公式:
\[Z_{i,j}=\frac{a_1-a_n* q}{1-q}\]
\[=\frac{\omega_n^0-\omega_n^{(n-1)* (j-i)}* \omega_n^{j-i}}{1-\omega_n^{j-i}}\]
\[=\frac{1-\omega_n^{n* (j-i)}}{1-\omega_n^{j-i}}\]
\[=\frac{1-1}{1-\omega_n^{j-i}}\]
\[=0\]
那么就得到
\[X* Y=nI\]
(\(I\)指单位矩阵)
\[X* \frac 1nY=I\]
\[X^{-1}=\frac 1nY\]
也就是说,我们只要把\(DFT\)过程中的点值选取\(\omega_n^i\)换成\(\omega_n^{-i}\),进行一次\(DFT\)后把结果除以\(n\)就可以了。
时间复杂度证明同上。
那么这就是\(FFT\)的过程了。
是不是很简单啊。
代码实现
首先是最基本的\(FFT\)。
采用简单的递归实现。
时间复杂度 \(O(nlog_2n)\)
空间复杂度 \(O(nlog_2n)\)
代码:
#include <cmath>
#include <cstdio>struct Complex//自定义复数,STL太慢
{double x,y;//x为实部,y为虚部inline Complex operator+(const Complex &a)//加法{return (Complex){x+a.x,y+a.y};}inline Complex operator-(const Complex &a)//减法{return (Complex){x-a.x,y-a.y};}inline Complex operator*(const Complex &a)//乘法{return (Complex){x*a.x-y*a.y,x*a.y+y*a.x};}//除法用不到就没写
}Pol[100005],Tmp[100005],Ome[100005],Inv[100005];
//Pol - 多项式 Tmp - 备用数组 Ome - 预处理\omega_n^i Inv - Ome的逆int n;//n=2^m
const double PI=acos(-1);void Pre()
{for(int i=0;i<n;++i){Ome[i]=(Complex){cos(2.0*PI*i/n), sin(2.0*PI*i/n)};Inv[i]=(Complex){cos(2.0*PI*i/n),-sin(2.0*PI*i/n)};}//简单的预处理
}void FFT(int Siz,int Lef,int Len)//Siz - 子问题大小 Lef - 区域最左端 Len - 步长(a0与a1的距离)
{if(Siz==1)return;int NSiz=Siz>>1;//下一个子问题FFT(NSiz,Lef,Len<<1),FFT(NSiz,Lef+NSiz,Len<<1);//递归处理for(int i=0;i<NSiz;++i){int Pos=Len*i<<1;Tmp[i]=Pol[Lef+Pos]+Ome[i*Len]*Pol[Lef+Pos+Len];//按照定义计算Tmp[i+NSiz]=Pol[Lef+Pos]-Ome[i*Len]*Pol[Lef+Pos+Len];}for(int i=0;i<Siz;++i)Pol[Lef+i*Len]=Tmp[i];//计算完毕
}int main(){Pre();FFT(n=65536,0,1);};
如果是\(IDFT\)把\(FFT\)中\(Ome\)改成\(Inv\)最后结果\(/n\)即可。
但是。。这个程序常数太大了!!(自带O(Inf)大常数)
我们来尝试优化程序。
非递归实现
发现,第一层递归将下标二进制中最后一位相同的元素分在了一起。(按奇偶性分类)
第二层将最后两位相同的分在了一起。
于是,同一组数二进制反转后是一段连续的区间(前几位相同,后几位包含所有情况)。
发现,\(i\)最后所在的位置是\(R_i\)(\(i\)的二进制反转)
先把所有数放到最后的位置上,最后向上合并即可。
时间复杂度 \(O(nlog_2n)\)
空间复杂度 \(O(nlog_2n)\)
代码:
#include <cmath>
#include <cstdio>
#include <algorithm>struct Complex//自定义复数,STL太慢
{double x,y;//x为实部,y为虚部inline Complex operator+(const Complex &a)//加法{return (Complex){x+a.x,y+a.y};}inline Complex operator-(const Complex &a)//减法{return (Complex){x-a.x,y-a.y};}inline Complex operator*(const Complex &a)//乘法{return (Complex){x*a.x-y*a.y,x*a.y+y*a.x};}//除法用不到就没写
}Pol[100005],Ome[100005],Inv[100005];
//Pol - 多项式 Ome - 预处理\omega_n^i Inv - Ome的逆int n;//n=2^m
const double PI=acos(-1);void Pre()
{for(int i=0;i<n;++i){Ome[i]=(Complex){cos(2.0*PI*i/n), sin(2.0*PI*i/n)};Inv[i]=(Complex){cos(2.0*PI*i/n),-sin(2.0*PI*i/n)};}//简单的预处理
}void FFT(Complex op[])
{for(int i=0,j=0;i<n;++i){if(i>j)std::swap(Pol[i],Pol[j]);//避免重复交换for(int l=n>>1;(j^=l)<l;l>>=1);//反向二进制加法}for(int i=2;i<=n;i<<=1)//现在处理的区间长度(从下往上){int m=i>>1;//区间子问题for(int j=0;j<n;j+=i)//对每一个区间计算一边for(int k=0;k<m;++k)//此区间的左边(k<i/2){Complex Tmp=op[n/i*k]*Pol[j+k+m];//避免额外内存开销(蝴蝶操作)Pol[j+k+m]=Pol[j+k]-Tmp;Pol[j+k]=Pol[j+k]+Tmp;}}
}int main(){n=65536;Pre();FFT(Ome);FFT(Inv);};
P3803 【模板】多项式乘法(FFT)
\(En,\)模板题。
因为乘起来有\(n+m\)次,要补足\(n+m\)。
时间复杂度 \(O(nlog_2n)\)
空间复杂度 \(O(nlog_2n)\)
代码:
#include <cmath>
#include <cstdio>
#include <cctype>
#include <algorithm>char File[1000005],*p1=File,*p2=File;inline char Getchar()
{return p1==p2&&(p2=(p1=File)+fread(File,1,1000000,stdin),p1==p2)?EOF:*p1++;
}inline int Getint()
{register int x=0,c;while(!isdigit(c=Getchar()));for(;isdigit(c);c=Getchar())x=x*10+(c^48);return x;
}struct Complex
{double x,y;inline Complex operator+(const Complex &a){return (Complex){x+a.x,y+a.y};}inline Complex operator-(const Complex &a){return (Complex){x-a.x,y-a.y};}inline Complex operator*(const Complex &a){return (Complex){x*a.x-y*a.y,x*a.y+y*a.x};}
}a[3000005],b[3000005],Ome[3000005],Inv[3000005];int n,m,Maxl;
const double PI=acos(-1);void Pre()
{for(register int i=0;i<n;++i){Ome[i]=(Complex){cos(2.0*PI*i/n),sin(2.0*PI*i/n)};Inv[i]=(Complex){cos(2.0*PI*i/n),sin(2.0*PI*-i/n)};}
}void FFT(Complex Pol[],Complex op[])
{for(int i=0,j=0;i<n;++i){if(i>j)std::swap(Pol[i],Pol[j]);for(int l=n>>1;(j^=l)<l;l>>=1);}for(register int i=2;i<=n;i<<=1){int m=i>>1;for(register int j=0;j<n;j+=i)for(register int k=0;k<m;++k){Complex Tmp=op[n/i*k]*Pol[j+k+m];Pol[j+k+m]=Pol[j+k]-Tmp;Pol[j+k]=Pol[j+k]+Tmp;}}
}int main()
{n=Getint(),m=Getint();for(register int i=0;i<=n;++i)a[i].x=Getint();for(register int i=0;i<=m;++i)b[i].x=Getint();for(Maxl=n+m,n=2;n<=Maxl;n<<=1);Pre();FFT(a,Ome),FFT(b,Ome);for(int i=0;i<n;++i)a[i]=a[i]*b[i];FFT(a,Inv);for(int i=0;i<=Maxl;++i)printf("%d%c",(int)floor(a[i].x/n+0.5),i==Maxl?'\n':' ');return 0;
}
【模板】A*B Problem升级版(FFT快速傅里叶)
~~我终于会写A*B了!!~~
把\(x\)看成\(10\)多项式乘法即可。
代码:
#include <cmath>
#include <cstdio>
#include <cctype>
#include <algorithm>char File[1000005],*p1=File,*p2=File;inline int Getint()
{register int c;while(!isdigit(c=getchar()));return c^48;
}struct Complex
{double x,y;inline Complex operator+(const Complex &a){return (Complex){x+a.x,y+a.y};}inline Complex operator-(const Complex &a){return (Complex){x-a.x,y-a.y};}inline Complex operator*(const Complex &a){return (Complex){x*a.x-y*a.y,x*a.y+y*a.x};}
}a[150005],b[150005],Ome[150005],Inv[150005];int n,Maxl,s[150005];
const double PI=acos(-1);void Pre()
{for(register int i=0;i<n;++i){Ome[i]=(Complex){cos(2.0*PI*i/n),sin(2.0*PI*i/n)};Inv[i]=(Complex){cos(2.0*PI*i/n),sin(2.0*PI*-i/n)};}
}void FFT(Complex Pol[],Complex op[])
{for(int i=0,j=0;i<n;++i){if(i>j)std::swap(Pol[i],Pol[j]);for(int l=n>>1;(j^=l)<l;l>>=1);}for(register int i=2;i<=n;i<<=1){int m=i>>1;for(register int j=0;j<n;j+=i)for(register int k=0;k<m;++k){Complex Tmp=op[n/i*k]*Pol[j+k+m];Pol[j+k+m]=Pol[j+k]-Tmp;Pol[j+k]=Pol[j+k]+Tmp;}}
}int main()
{scanf("%d",&n),--n;for(register int i=n;i>=0;--i)a[i].x=Getint();for(register int i=n;i>=0;--i)b[i].x=Getint();for(Maxl=n<<1,n=2;n<=Maxl;n<<=1);Pre();FFT(a,Ome),FFT(b,Ome);for(int i=0;i<n;++i)a[i]=a[i]*b[i];FFT(a,Inv);for(int i=0;i<=Maxl+5;++i){s[i]+=(int)floor(a[i].x/n+0.5);s[i+1]+=s[i]/10;s[i]%=10;}bool OK=false;for(int i=Maxl+5;i>=0;--i){if(s[i])OK=true;if(OK||!i)putchar(s[i]^48);}puts("");return 0;
}
总结
\(FFT\)太可怕了。。虽然联赛不至于考\((Flag)\),但是还是很有用的,巩固一下。
参考资料:(\(Dalao\ Orz\))
从多项式乘法到快速傅里叶变换-Miskcoo
小学生都能看懂的FFT!!!-胡小兔
\(2.Medium-NTT(FNT)\)
定义
NTT\((Number\ Theoretic\ Transforms)\)
(也称为\(Fast\ Number-Theoretic\ Transform\),简称\(FNT\))
中文名称:快速数论变换
(Not True Transforms)
\(Q:FFT\)懂了,\(NTT\)又有什么用呢?\(FFT\)已经够用了啊??
\(A:\)别急,相对于\(FFT\)来说,\(NTT\)具有更强的针对性,\(NTT\)可以在取模意义下进行多项式乘法计算,从而避免\(FFT\)的\(double\)失精的情况,但\(NTT\)对模数有特殊要求,这在下面会提到。
那么\(NTT\)是怎么实现的呢?
其实\(NTT\)的实现方法与\(FFT\)几乎无异,只需把复数运算换成取模运算即可。
现在来思考为什么\(FFT\)的点值表示要用单位根呢?
因为单位根有如下性质供\(FFT\)利用以加速:
- \(1.\)
\[\omega_n^n=1\]
这一点在\(DFT\)时需要用到
- \(2.\)
所有单位根互不相同,这样才能算出正确答案(例如\(n\)个\(n\)元方程组只有线性无关才有唯一解)。
- \(3.\)
\[\begin{cases} \omega_{2n}^{2k}=\omega_n^k(k<\frac n2)\\ \omega_n^{k+\frac n2}=-\omega_n^k(k\ge\frac n2) \end{cases}\]
显然这样分治才能继续进行
- \(4.\)
\[\sum_{k=0}^{n-1}\omega_n^{k(j-i)}= \begin{cases} 0(i\not=j)\\ n(i=j) \end{cases}\]
这一点\(IDFT\)时有需要。
所以说接下来我们需要找到合适的数满足上面几条性质来代替单位根。
原根
设有质数\(p\),则\(p\)的原根\(g\)满足\(g^k\mod p(1\le k<p-1)\)互不相同。
那么若质数\(p=q*n+1(n=2^x)\),则根据费马小定理有\(a^{p-1}\equiv 1(\mod p)\)
显然,\(g_0\equiv g_{p-1}\equiv 1(\mod p)\)
若设\(\omega_n=g^q\),则可以得到\(n\)个不相同的数:\(\omega_n^k(0\le k<n)\)
满足性质2
并且\(\omega_n^n\equiv g^{p-1}\equiv 1(\mod p)\)
满足性质1
那么就可以得到:
\(\because p=q*n+1=\frac q2*2n+1,\omega_n=g^q\)
\(\therefore \omega_{2n}=g^{\frac q2}\)
\(\omega_{2n}^{2k}=g^{\frac q2*2k}=g^{qk}=\omega_n^k\)
且
\(\omega_n^{k+\frac n2}\)
\(=\omega_n^k*\omega_n^{\frac n2}\)
\(\because (\omega_n^{\frac n2})^2=\omega_n^n=1\)
\(\therefore \omega_n^{\frac n2}=\pm1\)
\(\because \omega\)互不相同
\(\therefore \omega_n^{\frac n2}=-1\)
\(\therefore \omega_n^{k+\frac n2}=-\omega_n^k\)
满足性质3
最后:对于\(\sum_{k=0}^{n-1}\omega_n^{k(j-i)}\)
若\(i=j\),则:
\(\sum_{k=0}^{n-1}\omega_n^{k(j-i)}\)
\(=n*\omega_n^0\)
\(=n\)
若\(i\not=j\),则有:
\(\sum_{k=0}^{n-1}\omega_n^{k(j-i)}\)
\(=\frac{(q^n-1)a_0}{q-1}\)(等比数列求和,此处\(q\)为公比\((\omega_n^{j-i})\),\(a_0\)为首项\((\omega_n^0)\))
\(\because q^n-1=\omega_n^{n(j-i)}-1=(\omega_n^n)^{j-i}-1=0\)
\(\therefore \sum_{k=0}^{n-1}\omega_n^{k(j-i)}=0\)
综上所述,满足性质4
\(Q:\)什么?原根怎么求?
\(A:\)我怎么知道,百度啊
一般情况下只需要记住\(998244353\)的原根是\(3\)就好\((998244353=119*2^{23}+1)\),也可以查表:[Miskcoo's Space]FFT用到的各种素数
于是,照着上面说的,\(NTT\)的框架就出来了:
把复数运算换成取模即可。
\(Q:n\)不满\(2^{23}\)怎么办?补满太慢。
\(A:\)把\(\omega_n\)换成\(g^{\frac{p-1}{n}}\)即可。
P3803 【模板】多项式乘法(FFT)
\(Q:\)为什么是\(FFT\)模板?
\(A:\)找不到NTT的 因为这题答案不会超过\(998244353\),那么用来取模就并不会产生影响。
代码:
#include <cstdio>
#include <cctype>
#include <algorithm>char In[1000005],*p1=In,*p2=In;
#define Getchar (p1==p2&&(p2=(p1=In)+fread(In,1,1000000,stdin),p1==p2)?EOF:*p1++)
inline int Getint()
{register int x=0,c;while(!isdigit(c=Getchar));for(;isdigit(c);c=Getchar)x=x*10+(c^48);return x;
}const int p=998244353,g=3;int Pow(int a,int b)
{if(b<0)return Pow(Pow(a,p-2),-b);//逆元int Res=1;for(;b;b>>=1){if(b&1)Res=Res*1LL*a%p;a=a*1LL*a%p;}return Res%p;
}int n,m,Maxl;
int a[2100005],b[2100005];void NTT(int Pol[],int op)//op=1为DFT,-1为IDFT
{for(int i=0,j=0;i<n;++i){if(i>j)std::swap(Pol[i],Pol[j]);for(int l=n>>1;(j^=l)<l;l>>=1);}for(register int i=2;i<=n;i<<=1){int m=i>>1,Rs=Pow(g,op*(p-1)/i);for(register int j=0;j<n;j+=i){int Root=1;for(register int k=0;k<m;++k){int Tmp=Root*1LL*Pol[j+k+m]%p;Root=Root*1LL*Rs%p;//int Root=Pow(Omega,op*(p-1)/n*k)//不预处理单位根,使用秦九韶算法加速Pol[j+k+m]=Pol[j+k]-Tmp;Pol[j+k]=Pol[j+k]+Tmp;Pol[j+k+m]<0?Pol[j+k+m]+=p:0;//减少取模Pol[j+k]>=p?Pol[j+k]-=p:0;}}}
}int main()
{n=Getint(),m=Getint();for(register int i=0;i<=n;++i)a[i]=Getint();for(register int i=0;i<=m;++i)b[i]=Getint();for(Maxl=n+m,n=2;n<=Maxl;n<<=1);NTT(a,1),NTT(b,1);for(int i=0;i<n;++i)a[i]=a[i]*1LL*b[i]%p;NTT(a,-1);int Invn=Pow(n,p-2);for(int i=0;i<=Maxl;++i)printf("%d%c",int(a[i]*1LL*Invn%p),i==n-1?'\n':' ');//答案同样/nreturn 0;
}
相信有了\(FFT\)的基础,\(NTT\)应该很简单。
参考资料:(\(STO\ Dalao\))
从多项式乘法到快速傅里叶变换-Miskcoo
从傅里叶变换到数论变换-Menci
\(3.Hard-MTT\)
定义
[少女施工中]咕了
\(4.Extreme-FWT\)
FWT\((Fast\ Walsh-Hadamard\ Transform)\)
中文名称:快速沃尔什变换
(Fast Wrong-Answer Transform)
\(Q:\)有完没完了?\(FWT\)又是什么?现在已经能处理任意情况的多项式乘法了,还要这个干什么?
\(A:\)我也不想学啊,根本背不下来
虽然现在我们可以快速求出\(C=A*B,C_k=\sum_{i+j=k}A_i*B_j\)了,但是现在让你求\(C=A\oplus B,C_k=\sum_{i\oplus j=k}A_i*B_j\),其中\(\oplus\)代表一个位运算符号,如\(|(or),\&(and),\land(xor)\),你该怎么做呢?
这时就到\(FWT\)登场了。
接下来让我们对于\(FWT\)的\(3\)种形式感性理解分别讨论
\(Part1--FWT(or)\)
设\(A_0,A_1\)分别表示长度为\(n=2^x\)的多项式\(A\)的前半部分和后半部分。
首先,给出\(FWT(A)\)的计算方式:
\[ FWT(A)=\begin{cases} (FWT(A_0),FWT(A_0)+FWT(A_1))&(n>1)\\ A&(n=1) \end{cases} \]
其中\((A,B)\)表示两个多项式相连。
那么\(n=1\)是显然是对的,边界嘛。
至于\(n>1\)的情况如何理解?
对于\(A_0\)和\(A_0\)中两个数下标\(or\)起来一点还在\(A_0\)中(二进制下最高位为\(0\),是前半部分),那么就只对前半部分有贡献。
对于\(A_1\)和\(A_1\)中两个数,同理只对后半部分有贡献。
对于\(A_0\)和\(A_1\)中的两个数,思考\(FWT(A)_k\)的意义,有:
\[FWT(A)_k=\sum_{i|k=k}A_i\]
因为当\(i|k=k,j|k=k\)时,有\((i|j)|k=k\),满足\(FWT\)的可合并性质。
那么因为\(A_1\)下标二进制最高位为\(1\),所以\(or\)起来只对后半部分产生贡献。
贡献就是\(A_0\)对\(A_1\)的贡献(\(A_1\)已经贡献过自己了,不用再加)。
那么式子就很明显了。
同时根据\(FWT(A)\)的意义,容易发现\(FWT(A_0+A_1)=FWT(A_0)+FWT(A_1)\)。
接下来证明\(FWT(A|B)=FWT(A)*FWT(B)\)(保证\(or\)卷积答案的正确性,要不然\(FWT\)就没有用了)。
当\(n=1\)时,性质显然成立
当\(n>1\)时,:
\[ \begin{equation} \begin{split} FWT(A|B)=&FWT((A|B)_0,(A|B)_1)\\ &=FWT(A_0|B_0,A_0|B_1+A_1|B_0+A_1|B_1)\\ &=(FWT(A_0|B_0),FWT(A_0|B_0+A_0|B_1+A_1|B_0+A_1|B_1))\\ &=(FWT(A_0)*FWT(B_0),FWT(A_0)*FWT(B_0)+FWT(A_0)*FWT(B_1)\\ &+FWT(A_1)*FWT(B_0)+FWT(A_1)*FWT(B_1))\\ &=(FWT(A_0)*FWT(B_0),(FWT(A_0)+FWT(A_1))*(FWT(B_0)+FWT(B_1)))\\ &=(FWT(A_0)*FWT(B_0),FWT(A_0+A_1)*FWT(B_0+B_1)))\\ &=(FWT(A_0),FWT(A_0+A_1))*(FWT(B_0),FWT(B_0+B_1))\\ &=FWT(A)*FWT(B) \end{split} \end{equation} \]
由数学归纳法得知,此性质成立。
那么\(or\)的\(FWT\)就很好写了~~代码在后面。
\(Part2--FWT(and)\)
\(and\)的\(FWT\)就和\(or\)的很类似了。
因为\(A_0\)和\(A_1\)最高位不同,那么\(and\)后只对\(A_0\)有贡献。
类似\(or\)的,可以得到\(FWT(A)\)的计算方式:
\[ FWT(A)=\begin{cases} (FWT(A_0)+FWT(A_1),FWT(A_1))&(n>0)\\ A(n=0) \end{cases} \]
至于证明就不写了,和\(or\)的类似,写着麻烦。
\(Part3--FWT(xor)\)
最迷的\(xor\)来了
说实话,在网上找了许多\(Blog\),似乎都没有给出构造方法,那么我也不会啊
你就当是某位神仙找的规律吧
首先是\(FWT(A)\)的计算方式:
\[ FWT(A)=\begin{cases} (FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))&(n>0)\\ A(n=0) \end{cases} \]
看着都恶心,这怎么构造出来的啊\(QAQ\)
那么根据定义,很容易证明\(FWT(A\pm B)=FWT(A)\pm FWT(B)\)
因为\(FWT\)是一个线性组合,满足以上性质。
然后是\(FWT(A\land B)=FWT(A)*FWT(B)\)
这个也可以用数学归纳法证明,详见参考资料
\(Q:\)等等……是不是少了什么?\(FWT\)后怎么变回去呢?
\(A:\)这还不简单接下来的过程就是\(IFWT\)了!
\(Part4--IFWT(or)\)
\(Emm...\)至于\(IFWT\)呢就很简单了,把变换倒过来即可。
(这不是废话吗)
那么对于\(or\)的\(IFWT\),考虑之前有\(FWT\)的方程:
\[FWT(A)=(FWT(A_0),FWT(A_0)+FWT(A_1))\]
也就是:
\[FWT(A)_0=FWT(A_0),FWT(A)_1=FWT(A_0)+FWT(A_1)\]
\[FWT(A_0)=FWT(A)_0,FWT(A_1)=FWT(A_0)-FWT(A)_1=FWT(A)_0-FWT(A)_1\]
此时定义\(IFWT(A)_0=FWT(A_0),IFWT(A)_1=FWT(A_1)\) ,也就有:
\[ IFWT(A)=\begin{cases} (IFWT(A_0),IFWT(A_0)-IFWT(A_1))&(n>0)\\ A&(n=0) \end{cases} \]
\(En...\)真简单
\(Part5--IFWT(and)\)
类似\(or\)的\(IFWT\),可以直接得到:
\[ IFWT(A)=\begin{cases} (IFWT(A_0)-IFWT(A_1),IFWT(A_1))&(n>0)\\ A(n=0) \end{cases} \]
过程类似,这里就不多赘述。。
\(Part6--IFWT(xor)\)
\(xor\)的\(IFWT\)出人意料地一样简单。
由定义得:
\[ \begin{cases} FWT(A)_0=FWT(A_0)+FWT(A_1)\\ FWT(A)_1=FWT(A_0)-FWT(A_1) \end{cases} \]
解方程就简单了。
最后有:
\[ IFWT(A)=\begin{cases} (\frac{IFWT(A_0)+IFWT(A_1)}2,\frac{IFWT(A_0)-IFWT(A_1)}2)&(n>0)\\ A&(n=0) \end{cases} \]
终于完了
那么接下来就是看图写话看定义写代码过程了:
这里为了节省代码量把\(6\)个函数写一起了(因为框架大致类似)。
P4717 【模板】快速沃尔什变换
代码:
#include <cstdio>
#include <cstring>
typedef long long ll;const int Mod=998244353,Inv2=(Mod+1)>>1;//Inv2 2在mod998244353下的逆元
int n,a[1<<17],b[1<<17],as[1<<17],bs[1<<17];void FWT(int *A,int op,int t)
//op [1/-1][FWT/IFWT]
//t [1,2,3][or/and/xor]
{for(int i=2;i<=n;i<<=1)//i 区间长度for(int j=0,m=i>>1;j<n;j+=i)//j 区间左端 m 区间大小一半for(int k=0;k<m;++k)//k 正在算第几个数if(t==1)A[j+m+k]=((ll)A[j+m+k]+A[j+k]*op+Mod)%Mod;else if(t==2)A[j+k]=((ll)A[j+k]+A[j+m+k]*op+Mod)%Mod;else{int A0=A[j+k],A1=A[j+m+k];A[j+k]=(ll)(A0+A1)*(op==1?1:Inv2)%Mod;A[j+m+k]=(ll)(A0-A1+Mod)*(op==1?1:Inv2)%Mod;}
}int main()
{scanf("%d",&n),n=1<<n;for(int i=0;i<n;++i)scanf("%d",&as[i]);for(int i=0;i<n;++i)scanf("%d",&bs[i]);for(int t=1;t<=3;++t)//分别计算or/and/xor{memcpy(a,as,sizeof(int)*n);memcpy(b,bs,sizeof(int)*n);FWT(a,1,t),FWT(b,1,t);for(int i=0;i<n;++i)a[i]=a[i]*1LL*b[i]%Mod;FWT(a,-1,t);for(int i=0;i<n;++i)printf("%d%c",a[i],i==n-1?'\n':' ');}return 0;
}
代码应该很好懂,就不解释了。
我只能说:\(FWT\)真好背真好写。
参考资料:(\(Dalao\ TQL\))
FWT快速沃尔什变换学习笔记-小蒟蒻yyb
关于快速沃尔什变换(FWT)的一点学习和思考-ACMLCZH
后记
终于写完了\(MTT\)有空再补吧。。
这应该时我耗时最长的一篇\(blog\)了(目前为止),如有错误请在评论区指出。
学了这么多多项式,感觉收获不错虽然不会用
看了一下好像还有\(FMT\)(快速莫比乌斯变换),太可怕了吧。。
我大概一辈子也不会碰吧\((Flag)\)。
转载于:https://www.cnblogs.com/LanrTabe/p/10266602.html
如若内容造成侵权/违法违规/事实不符,请联系编程学习网邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
相关文章
- java正则匹配json
有些时候如果json格式数据里如果value带有双引号,则这样的数据无法直接用json工具解析出来,需要手动去处理,下边的正则表达式匹配出带有双引号的value。String str="{\"keyword\":\"xin \"hua\",\"type\":\"news\",\"…...
2024/4/17 1:06:17 - Gradle学习笔记 使用插件
前面说了不少内容,但是我看了一下Gradle官方文档内容太多太详细。其中大部分内容其实我们不需要知道。一般情况下我们应用一部分插件就可以了。自己编写Gradle任务的情况并不多见。Java插件在build.gradle文件中添加以下一句,即可启用Java插件。Java插件用于构建普通的Java项…...
2024/5/7 21:19:13 - Openssl中的BIGNUM运算函数(整理)
目录1.初始化函数2.上下文结构3.与 字符/位 相关的函数4.计算类函数5.随机函数最近在学习BIGNUM的使用,但是奈何在项目中看到一个函数总是不认识...网上能搜到的表格又极其少...所以选择自己手动整理一份自认为较为完整的函数表格,不定时更新1.初始化函数函数原型解释示例BIGNU…...
2024/5/7 21:06:44 - 【BZOJ4589】Hard Nim(FWT)
【BZOJ4589】Hard Nim(FWT) 题面 BZOJ Description Claris和NanoApe在玩石子游戏,他们有n堆石子,规则如下: Claris和NanoApe两个人轮流拿石子,Claris先拿。 每次只能从一堆中取若干个,可将一堆全取走,但不可不取,拿到最后1颗石子的人获胜。 不同的初始局面,决定了最终…...
2024/5/7 14:21:28 - 正则匹配 或者 整个单词
像本地开发中经常需要匹配localhost和127.0.0.1我们就可以使用:/(localhost|127.0.0.1)/.test(location.hostname)这里用括号代表一个整体,如果用的中括号[],就是别的意思了/[localhost|127.0.0.1]/.test(location.hostname)这个代表只要可以匹配中括号的任意一个字符就好了,…...
2024/4/17 1:06:05 - mcp918使用教程(MineCraft 1.8.8反编译)
MC src获取过程(本文作为学习参考使用,请勿用于其他途径,请在12小时内删除本文相关下载内容。阅读下文则默认同意本协议)相关文件网盘链接:https://pan.baidu.com/s/1m5Ur6MZJfnqIjXgLvyqUYQ 提取码:gcbnMC登录相关操作参考:https://www.mcbbs.net/thread-38297-1-1.…...
2024/5/8 4:34:32 - 所有游戏类型简称的意思
ACT :ACTION.动作游戏.A.RPG :ACTION ROLE PLAYING GAME.动作角色扮演游戏. AVG :ADVENTURE GAME.冒险游戏.A.AVG :ACTION ADVENTURE GAME.动作冒险游戏.RPG :ROLE PLAYING GAME.角色扮演游戏.ETC :其他类游戏.FPS :FIRST PERSON SHOOTING .第一人称射击游戏.FTG :FIGHTING GAM…...
2024/5/8 0:36:50 - Eclipse安装CXF插件开发java web service 集成Spring
本文主要介绍在Eclipse[3.3.2]安装CXF插件。开发一个简单的java web service,以及和Spring的集成。 安装插件: 1,下载STP all_in_one,从http://ftp.daum.net/eclipse/stp/old-downloads-page/可以下载stp-all-in-one-incubation-0.7.0.200711162004.zip 安装这个插件,可以…...
2024/5/7 13:56:00 - IDA反编译器的使用
IDA反编译器,正如IDA官网所说,虽然还原出来的代码不能直接使用,但是其参考作用不容否认。这里记录一些反编译时会用到的功能。1.生成伪代码:view-Open subviews-Generate pesudocode (快捷键F5)->(F5前后对比图)2.伪代码切换到对应的反汇编代码:前面说了,IDA生成的伪代…...
2024/4/20 10:34:16 - FFT/NTT/FWT专题
FFT可快速计算卷积,卷积为两个生成函数的乘积,生成函数为FFT 卷积 生成函数 的关系多项式 之 快速傅里叶变换(FFT)/数论变换(NTT)/例题与常用套路【入门】HDU1402 A * B Problem Plus大数乘法生成函数:,设两个大数位:、,L1/L2为两个大数的长度,利用FFT求两个函数的卷积,将…...
2024/4/17 1:07:58 - 正则匹配数组全部是数字
var value=["2","3"]v ar v= value.join(""); var reg = /^\d+$/g;if(!v.match(reg)){//是否匹配到了数字,未匹配到就不是return;}if(v.match(reg)[0].length<v.length){//匹配到的数字等于v的长度return;}...
2024/5/7 19:03:30 - golang 理解 reflect包 函数 ValueOf, Value.Set
最近golang 项目需要一个通用函数,更新结构体中的数据。查看资料需要用到反射机制,之前对反射机制理解不深,费了些周折,终于有所理解,记录于此,供自己和大家参考。理解interface{}变量理解reflect 机制很重要一点,本人觉得关键需要理解把一个变量传给下面例子函数的inte…...
2024/4/19 6:14:30 - java操作LibreOffice插件
领导不知道在哪看到libreoffice说要用这个把office转为pdf,于是本人各种翻资料,总结发现jodconverter-3.0 以上版本支持java代码调用。此包找了很久最后花钱下载,有要的@我 qq857484261<!-- https://mvnrepository.com/artifact/org.jodconverter/jodconverter-local --&…...
2024/5/7 20:49:20 - android之cmd手工反编译笔记
Android反编译教程 ——西北狼 更新~~~~~~~~~~~偶遇的一篇较新的APK反编译文章:http://blog.csdn.net/XiNanHeiShao/article/details/74278192---------------------------------------------------------------------------------------------------------------------------…...
2024/4/17 1:06:05 - js正则匹配多个全部数据
需求:获取所有title里的内容正则表达式后面加g表示多次匹配方式一:match 返回数组方式二exec<script>var str=<a href="//www.aliexpress.com/store/product/OOOT-BAORJCT-174296-22mm-10yard-lot-cartoon-Ribbons-Thermal-transfer-Printed-grosgrain-Wedding…...
2024/4/17 1:07:04 - [Python] TypeError: 'set' object is not callable”解决方案
Python set set() 函数创建一个无序不重复元素集,可进行关系测试,删除重复数据,还可以计算交集、差集、并集等。 注:set中无index 今天读取两个文件合并,并去重。文件格式如下:下面程序在29行报错’set’ object is not callable(当前程序中注释掉的行),此错误表示您可…...
2024/5/7 22:51:29 - K 进制 FWT 学习笔记
需要快速求出 Ck=∑i⨂j=kAi∗BjC_k=\sum_{i\bigotimes j=k}A_i*B_jCk=∑i⨂j=kAi∗Bj 考虑构造一个可逆的矩阵满足 (f∗A)∗(f∗B)=(f∗C)(f*A)*(f*B)=(f*C)(f∗A)∗(f∗B)=(f∗C) 那么只需要快速求出 f∗A,f∗B,f−1∗(f∗C)f*A,f*B,f^{-1}*(f*C)f∗A,f∗B,f−1∗(f∗…...
2024/4/18 9:11:40 - 正则匹配手机号
匹配手机号/^1[0-9]{10}$/ /^1\d{10}$/匹配异常的手机号/^((?!1[0-9]{10}).)*$/PHP// 匹配正常的手机号(以 1 开头的 11 位数字) preg_match("/^1[0-9]{10}$/", $mobile); preg_match("/^1\d{10}$/", $mobile);// 诸如 " 13012341234"、&quo…...
2024/4/17 7:00:12 - Gradle编译java,Eclipse项目以及遇到的问题
使用Gradle创建一个简单java项目步骤:1、 首先创建一个空的文件夹(名字随便起),我起名加gradlework2、 进入空文件夹,在命令行使用gradle init 初始化gradle结构3、 打开编辑build.gradle文件,添加java插件并添加eclipse插件,然后添加创建java文件目录 代码如下 apply p…...
2024/5/1 4:04:29 - UOJ310. 【UNR #2】黎明前的巧克力 [FWT]
UOJ 思路 显然可以转化一下,变成统计异或起来等于0的集合个数,这样一个集合的贡献是\(2^{|S|}\)。 考虑朴素的\(dp_{i,j}\)表示前\(i\)个数凑出了\(j\)的方案数,发现这其实就是一堆多项式用异或卷积搞起来。第\(i\)个多项式是\(1+2x^{a_i}\)。 对\(1+2x^{a}\)FWT一下,发现结…...
2024/4/18 15:53:16
最新文章
- 【极速前进】20240423-20240428:Phi-3、fDPO、TextSquare多模态合成数据、遵循准则而不是偏好标签、混合LoRA专家
一、Phi-3技术报告 论文地址:https://arxiv.org/pdf/2404.14219 发布了phi-3-mini,一个在3.3T token上训练的3.8B模型。在学术基准和内部测试中的效果都优于Mixtral 8*7B和GPT-3.5。此外,还发布了7B和14B模型phi-3-small和phi-3-medium。…...
2024/5/8 4:58:22 - 梯度消失和梯度爆炸的一些处理方法
在这里是记录一下梯度消失或梯度爆炸的一些处理技巧。全当学习总结了如有错误还请留言,在此感激不尽。 权重和梯度的更新公式如下: w w − η ⋅ ∇ w w w - \eta \cdot \nabla w ww−η⋅∇w 个人通俗的理解梯度消失就是网络模型在反向求导的时候出…...
2024/5/7 10:36:02 - C# 抽象类、接口
(1)、抽象类和抽象方法的定义和实现:abstract override abstract class Vehicle{ public abstract void Run(); } 继承抽象类并且实现抽象方法 class RaceCar : Vehicle{ public override void Run(){ } } (2)、接口的…...
2024/5/6 11:49:43 - 爬虫学习第一天
爬虫-1 爬虫学习第一天1、什么是爬虫2、爬虫的工作原理3、爬虫核心4、爬虫的合法性5、爬虫框架6、爬虫的挑战7、难点8、反爬手段8.1、Robots协议8.2、检查 User-Agent8.3、ip限制8.4、SESSION访问限制8.5、验证码8.6、数据动态加载8.7、数据加密-使用加密算法 9、用python学习爬…...
2024/5/7 2:16:01 - 【外汇早评】美通胀数据走低,美元调整
原标题:【外汇早评】美通胀数据走低,美元调整昨日美国方面公布了新一期的核心PCE物价指数数据,同比增长1.6%,低于前值和预期值的1.7%,距离美联储的通胀目标2%继续走低,通胀压力较低,且此前美国一季度GDP初值中的消费部分下滑明显,因此市场对美联储后续更可能降息的政策…...
2024/5/7 5:50:09 - 【原油贵金属周评】原油多头拥挤,价格调整
原标题:【原油贵金属周评】原油多头拥挤,价格调整本周国际劳动节,我们喜迎四天假期,但是整个金融市场确实流动性充沛,大事频发,各个商品波动剧烈。美国方面,在本周四凌晨公布5月份的利率决议和新闻发布会,维持联邦基金利率在2.25%-2.50%不变,符合市场预期。同时美联储…...
2024/5/7 9:45:25 - 【外汇周评】靓丽非农不及疲软通胀影响
原标题:【外汇周评】靓丽非农不及疲软通胀影响在刚结束的周五,美国方面公布了新一期的非农就业数据,大幅好于前值和预期,新增就业重新回到20万以上。具体数据: 美国4月非农就业人口变动 26.3万人,预期 19万人,前值 19.6万人。 美国4月失业率 3.6%,预期 3.8%,前值 3…...
2024/5/4 23:54:56 - 【原油贵金属早评】库存继续增加,油价收跌
原标题:【原油贵金属早评】库存继续增加,油价收跌周三清晨公布美国当周API原油库存数据,上周原油库存增加281万桶至4.692亿桶,增幅超过预期的74.4万桶。且有消息人士称,沙特阿美据悉将于6月向亚洲炼油厂额外出售更多原油,印度炼油商预计将每日获得至多20万桶的额外原油供…...
2024/5/7 14:25:14 - 【外汇早评】日本央行会议纪要不改日元强势
原标题:【外汇早评】日本央行会议纪要不改日元强势近两日日元大幅走强与近期市场风险情绪上升,避险资金回流日元有关,也与前一段时间的美日贸易谈判给日本缓冲期,日本方面对汇率问题也避免继续贬值有关。虽然今日早间日本央行公布的利率会议纪要仍然是支持宽松政策,但这符…...
2024/5/4 23:54:56 - 【原油贵金属早评】欧佩克稳定市场,填补伊朗问题的影响
原标题:【原油贵金属早评】欧佩克稳定市场,填补伊朗问题的影响近日伊朗局势升温,导致市场担忧影响原油供给,油价试图反弹。此时OPEC表态稳定市场。据消息人士透露,沙特6月石油出口料将低于700万桶/日,沙特已经收到石油消费国提出的6月份扩大出口的“适度要求”,沙特将满…...
2024/5/4 23:55:05 - 【外汇早评】美欲与伊朗重谈协议
原标题:【外汇早评】美欲与伊朗重谈协议美国对伊朗的制裁遭到伊朗的抗议,昨日伊朗方面提出将部分退出伊核协议。而此行为又遭到欧洲方面对伊朗的谴责和警告,伊朗外长昨日回应称,欧洲国家履行它们的义务,伊核协议就能保证存续。据传闻伊朗的导弹已经对准了以色列和美国的航…...
2024/5/4 23:54:56 - 【原油贵金属早评】波动率飙升,市场情绪动荡
原标题:【原油贵金属早评】波动率飙升,市场情绪动荡因中美贸易谈判不安情绪影响,金融市场各资产品种出现明显的波动。随着美国与中方开启第十一轮谈判之际,美国按照既定计划向中国2000亿商品征收25%的关税,市场情绪有所平复,已经开始接受这一事实。虽然波动率-恐慌指数VI…...
2024/5/7 11:36:39 - 【原油贵金属周评】伊朗局势升温,黄金多头跃跃欲试
原标题:【原油贵金属周评】伊朗局势升温,黄金多头跃跃欲试美国和伊朗的局势继续升温,市场风险情绪上升,避险黄金有向上突破阻力的迹象。原油方面稍显平稳,近期美国和OPEC加大供给及市场需求回落的影响,伊朗局势并未推升油价走强。近期中美贸易谈判摩擦再度升级,美国对中…...
2024/5/4 23:54:56 - 【原油贵金属早评】市场情绪继续恶化,黄金上破
原标题:【原油贵金属早评】市场情绪继续恶化,黄金上破周初中国针对于美国加征关税的进行的反制措施引发市场情绪的大幅波动,人民币汇率出现大幅的贬值动能,金融市场受到非常明显的冲击。尤其是波动率起来之后,对于股市的表现尤其不安。隔夜美国股市出现明显的下行走势,这…...
2024/5/6 1:40:42 - 【外汇早评】美伊僵持,风险情绪继续升温
原标题:【外汇早评】美伊僵持,风险情绪继续升温昨日沙特两艘油轮再次发生爆炸事件,导致波斯湾局势进一步恶化,市场担忧美伊可能会出现摩擦生火,避险品种获得支撑,黄金和日元大幅走强。美指受中美贸易问题影响而在低位震荡。继5月12日,四艘商船在阿联酋领海附近的阿曼湾、…...
2024/5/4 23:54:56 - 【原油贵金属早评】贸易冲突导致需求低迷,油价弱势
原标题:【原油贵金属早评】贸易冲突导致需求低迷,油价弱势近日虽然伊朗局势升温,中东地区几起油船被袭击事件影响,但油价并未走高,而是出于调整结构中。由于市场预期局势失控的可能性较低,而中美贸易问题导致的全球经济衰退风险更大,需求会持续低迷,因此油价调整压力较…...
2024/5/4 23:55:17 - 氧生福地 玩美北湖(上)——为时光守候两千年
原标题:氧生福地 玩美北湖(上)——为时光守候两千年一次说走就走的旅行,只有一张高铁票的距离~ 所以,湖南郴州,我来了~ 从广州南站出发,一个半小时就到达郴州西站了。在动车上,同时改票的南风兄和我居然被分到了一个车厢,所以一路非常愉快地聊了过来。 挺好,最起…...
2024/5/7 9:26:26 - 氧生福地 玩美北湖(中)——永春梯田里的美与鲜
原标题:氧生福地 玩美北湖(中)——永春梯田里的美与鲜一觉醒来,因为大家太爱“美”照,在柳毅山庄去寻找龙女而错过了早餐时间。近十点,向导坏坏还是带着饥肠辘辘的我们去吃郴州最富有盛名的“鱼头粉”。说这是“十二分推荐”,到郴州必吃的美食之一。 哇塞!那个味美香甜…...
2024/5/4 23:54:56 - 氧生福地 玩美北湖(下)——奔跑吧骚年!
原标题:氧生福地 玩美北湖(下)——奔跑吧骚年!让我们红尘做伴 活得潇潇洒洒 策马奔腾共享人世繁华 对酒当歌唱出心中喜悦 轰轰烈烈把握青春年华 让我们红尘做伴 活得潇潇洒洒 策马奔腾共享人世繁华 对酒当歌唱出心中喜悦 轰轰烈烈把握青春年华 啊……啊……啊 两…...
2024/5/4 23:55:06 - 扒开伪装医用面膜,翻六倍价格宰客,小姐姐注意了!
原标题:扒开伪装医用面膜,翻六倍价格宰客,小姐姐注意了!扒开伪装医用面膜,翻六倍价格宰客!当行业里的某一品项火爆了,就会有很多商家蹭热度,装逼忽悠,最近火爆朋友圈的医用面膜,被沾上了污点,到底怎么回事呢? “比普通面膜安全、效果好!痘痘、痘印、敏感肌都能用…...
2024/5/5 8:13:33 - 「发现」铁皮石斛仙草之神奇功效用于医用面膜
原标题:「发现」铁皮石斛仙草之神奇功效用于医用面膜丽彦妆铁皮石斛医用面膜|石斛多糖无菌修护补水贴19大优势: 1、铁皮石斛:自唐宋以来,一直被列为皇室贡品,铁皮石斛生于海拔1600米的悬崖峭壁之上,繁殖力差,产量极低,所以古代仅供皇室、贵族享用 2、铁皮石斛自古民间…...
2024/5/4 23:55:16 - 丽彦妆\医用面膜\冷敷贴轻奢医学护肤引导者
原标题:丽彦妆\医用面膜\冷敷贴轻奢医学护肤引导者【公司简介】 广州华彬企业隶属香港华彬集团有限公司,专注美业21年,其旗下品牌: 「圣茵美」私密荷尔蒙抗衰,产后修复 「圣仪轩」私密荷尔蒙抗衰,产后修复 「花茵莳」私密荷尔蒙抗衰,产后修复 「丽彦妆」专注医学护…...
2024/5/4 23:54:58 - 广州械字号面膜生产厂家OEM/ODM4项须知!
原标题:广州械字号面膜生产厂家OEM/ODM4项须知!广州械字号面膜生产厂家OEM/ODM流程及注意事项解读: 械字号医用面膜,其实在我国并没有严格的定义,通常我们说的医美面膜指的应该是一种「医用敷料」,也就是说,医用面膜其实算作「医疗器械」的一种,又称「医用冷敷贴」。 …...
2024/5/6 21:42:42 - 械字号医用眼膜缓解用眼过度到底有无作用?
原标题:械字号医用眼膜缓解用眼过度到底有无作用?医用眼膜/械字号眼膜/医用冷敷眼贴 凝胶层为亲水高分子材料,含70%以上的水分。体表皮肤温度传导到本产品的凝胶层,热量被凝胶内水分子吸收,通过水分的蒸发带走大量的热量,可迅速地降低体表皮肤局部温度,减轻局部皮肤的灼…...
2024/5/4 23:54:56 - 配置失败还原请勿关闭计算机,电脑开机屏幕上面显示,配置失败还原更改 请勿关闭计算机 开不了机 这个问题怎么办...
解析如下:1、长按电脑电源键直至关机,然后再按一次电源健重启电脑,按F8健进入安全模式2、安全模式下进入Windows系统桌面后,按住“winR”打开运行窗口,输入“services.msc”打开服务设置3、在服务界面,选中…...
2022/11/19 21:17:18 - 错误使用 reshape要执行 RESHAPE,请勿更改元素数目。
%读入6幅图像(每一幅图像的大小是564*564) f1 imread(WashingtonDC_Band1_564.tif); subplot(3,2,1),imshow(f1); f2 imread(WashingtonDC_Band2_564.tif); subplot(3,2,2),imshow(f2); f3 imread(WashingtonDC_Band3_564.tif); subplot(3,2,3),imsho…...
2022/11/19 21:17:16 - 配置 已完成 请勿关闭计算机,win7系统关机提示“配置Windows Update已完成30%请勿关闭计算机...
win7系统关机提示“配置Windows Update已完成30%请勿关闭计算机”问题的解决方法在win7系统关机时如果有升级系统的或者其他需要会直接进入一个 等待界面,在等待界面中我们需要等待操作结束才能关机,虽然这比较麻烦,但是对系统进行配置和升级…...
2022/11/19 21:17:15 - 台式电脑显示配置100%请勿关闭计算机,“准备配置windows 请勿关闭计算机”的解决方法...
有不少用户在重装Win7系统或更新系统后会遇到“准备配置windows,请勿关闭计算机”的提示,要过很久才能进入系统,有的用户甚至几个小时也无法进入,下面就教大家这个问题的解决方法。第一种方法:我们首先在左下角的“开始…...
2022/11/19 21:17:14 - win7 正在配置 请勿关闭计算机,怎么办Win7开机显示正在配置Windows Update请勿关机...
置信有很多用户都跟小编一样遇到过这样的问题,电脑时发现开机屏幕显现“正在配置Windows Update,请勿关机”(如下图所示),而且还需求等大约5分钟才干进入系统。这是怎样回事呢?一切都是正常操作的,为什么开时机呈现“正…...
2022/11/19 21:17:13 - 准备配置windows 请勿关闭计算机 蓝屏,Win7开机总是出现提示“配置Windows请勿关机”...
Win7系统开机启动时总是出现“配置Windows请勿关机”的提示,没过几秒后电脑自动重启,每次开机都这样无法进入系统,此时碰到这种现象的用户就可以使用以下5种方法解决问题。方法一:开机按下F8,在出现的Windows高级启动选…...
2022/11/19 21:17:12 - 准备windows请勿关闭计算机要多久,windows10系统提示正在准备windows请勿关闭计算机怎么办...
有不少windows10系统用户反映说碰到这样一个情况,就是电脑提示正在准备windows请勿关闭计算机,碰到这样的问题该怎么解决呢,现在小编就给大家分享一下windows10系统提示正在准备windows请勿关闭计算机的具体第一种方法:1、2、依次…...
2022/11/19 21:17:11 - 配置 已完成 请勿关闭计算机,win7系统关机提示“配置Windows Update已完成30%请勿关闭计算机”的解决方法...
今天和大家分享一下win7系统重装了Win7旗舰版系统后,每次关机的时候桌面上都会显示一个“配置Windows Update的界面,提示请勿关闭计算机”,每次停留好几分钟才能正常关机,导致什么情况引起的呢?出现配置Windows Update…...
2022/11/19 21:17:10 - 电脑桌面一直是清理请关闭计算机,windows7一直卡在清理 请勿关闭计算机-win7清理请勿关机,win7配置更新35%不动...
只能是等着,别无他法。说是卡着如果你看硬盘灯应该在读写。如果从 Win 10 无法正常回滚,只能是考虑备份数据后重装系统了。解决来方案一:管理员运行cmd:net stop WuAuServcd %windir%ren SoftwareDistribution SDoldnet start WuA…...
2022/11/19 21:17:09 - 计算机配置更新不起,电脑提示“配置Windows Update请勿关闭计算机”怎么办?
原标题:电脑提示“配置Windows Update请勿关闭计算机”怎么办?win7系统中在开机与关闭的时候总是显示“配置windows update请勿关闭计算机”相信有不少朋友都曾遇到过一次两次还能忍但经常遇到就叫人感到心烦了遇到这种问题怎么办呢?一般的方…...
2022/11/19 21:17:08 - 计算机正在配置无法关机,关机提示 windows7 正在配置windows 请勿关闭计算机 ,然后等了一晚上也没有关掉。现在电脑无法正常关机...
关机提示 windows7 正在配置windows 请勿关闭计算机 ,然后等了一晚上也没有关掉。现在电脑无法正常关机以下文字资料是由(历史新知网www.lishixinzhi.com)小编为大家搜集整理后发布的内容,让我们赶快一起来看一下吧!关机提示 windows7 正在配…...
2022/11/19 21:17:05 - 钉钉提示请勿通过开发者调试模式_钉钉请勿通过开发者调试模式是真的吗好不好用...
钉钉请勿通过开发者调试模式是真的吗好不好用 更新时间:2020-04-20 22:24:19 浏览次数:729次 区域: 南阳 > 卧龙 列举网提醒您:为保障您的权益,请不要提前支付任何费用! 虚拟位置外设器!!轨迹模拟&虚拟位置外设神器 专业用于:钉钉,外勤365,红圈通,企业微信和…...
2022/11/19 21:17:05 - 配置失败还原请勿关闭计算机怎么办,win7系统出现“配置windows update失败 还原更改 请勿关闭计算机”,长时间没反应,无法进入系统的解决方案...
前几天班里有位学生电脑(windows 7系统)出问题了,具体表现是开机时一直停留在“配置windows update失败 还原更改 请勿关闭计算机”这个界面,长时间没反应,无法进入系统。这个问题原来帮其他同学也解决过,网上搜了不少资料&#x…...
2022/11/19 21:17:04 - 一个电脑无法关闭计算机你应该怎么办,电脑显示“清理请勿关闭计算机”怎么办?...
本文为你提供了3个有效解决电脑显示“清理请勿关闭计算机”问题的方法,并在最后教给你1种保护系统安全的好方法,一起来看看!电脑出现“清理请勿关闭计算机”在Windows 7(SP1)和Windows Server 2008 R2 SP1中,添加了1个新功能在“磁…...
2022/11/19 21:17:03 - 请勿关闭计算机还原更改要多久,电脑显示:配置windows更新失败,正在还原更改,请勿关闭计算机怎么办...
许多用户在长期不使用电脑的时候,开启电脑发现电脑显示:配置windows更新失败,正在还原更改,请勿关闭计算机。。.这要怎么办呢?下面小编就带着大家一起看看吧!如果能够正常进入系统,建议您暂时移…...
2022/11/19 21:17:02 - 还原更改请勿关闭计算机 要多久,配置windows update失败 还原更改 请勿关闭计算机,电脑开机后一直显示以...
配置windows update失败 还原更改 请勿关闭计算机,电脑开机后一直显示以以下文字资料是由(历史新知网www.lishixinzhi.com)小编为大家搜集整理后发布的内容,让我们赶快一起来看一下吧!配置windows update失败 还原更改 请勿关闭计算机&#x…...
2022/11/19 21:17:01 - 电脑配置中请勿关闭计算机怎么办,准备配置windows请勿关闭计算机一直显示怎么办【图解】...
不知道大家有没有遇到过这样的一个问题,就是我们的win7系统在关机的时候,总是喜欢显示“准备配置windows,请勿关机”这样的一个页面,没有什么大碍,但是如果一直等着的话就要两个小时甚至更久都关不了机,非常…...
2022/11/19 21:17:00 - 正在准备配置请勿关闭计算机,正在准备配置windows请勿关闭计算机时间长了解决教程...
当电脑出现正在准备配置windows请勿关闭计算机时,一般是您正对windows进行升级,但是这个要是长时间没有反应,我们不能再傻等下去了。可能是电脑出了别的问题了,来看看教程的说法。正在准备配置windows请勿关闭计算机时间长了方法一…...
2022/11/19 21:16:59 - 配置失败还原请勿关闭计算机,配置Windows Update失败,还原更改请勿关闭计算机...
我们使用电脑的过程中有时会遇到这种情况,当我们打开电脑之后,发现一直停留在一个界面:“配置Windows Update失败,还原更改请勿关闭计算机”,等了许久还是无法进入系统。如果我们遇到此类问题应该如何解决呢࿰…...
2022/11/19 21:16:58 - 如何在iPhone上关闭“请勿打扰”
Apple’s “Do Not Disturb While Driving” is a potentially lifesaving iPhone feature, but it doesn’t always turn on automatically at the appropriate time. For example, you might be a passenger in a moving car, but your iPhone may think you’re the one dri…...
2022/11/19 21:16:57