NanoApe's Blog


【数论】FMT 和 FWT

NanoApe posted @ 2016年6月30日 16:07 in 蒟蒻不撕烤智熵何来 , 4397 阅读





设当前长度为 $2^n$,按第 $n-1$ 位分成两部分(0为左1为右)后计算 $X=(f^L+f^R)*(g^L+g^R)$ 和 $Y=f^R*g^R$,左边等于 $X-Y$,右边等于 $Y$


$$F_S=\sum_{T \subseteq S} f_T$$

快速构造:$f_{S \cup i}←f_{S \cup i}+f_S$


$$f_S=\sum_{T \subseteq S} (-1)^{|S|-|T|}F_T$$

快速构造:$f_{S \cup i}←f_{S \cup i}-f_S$




设当前长度为 $2^n$,按第 $n-1$ 位分成两部分(0为左1为右)后计算 $X=(f^L+f^R)*(g^L+g^R)$ 和 $Y=(f^L-f^R)*(g^L-g^R)$,左边等于 $(X+Y)/2$,右边等于 $(X-Y)/2$


$$F_S=\sum_{T} f_T(-1)^{|S \cap T|}$$

快速构造:$f_{S}←f_S+f_{S \cup i},~f_{S \cup i}←f_S-f_{S \cup i}$

逆操作时最后乘上 $\frac{1}{2^n}$

inline void fwt()
	for(int i=1,x,y; i<m; i<<=1) 
		rep(o, 0, m-1) if (o&i) 
			x=f[o-i], y=f[o], 
			f[o-i]=x+y, f[o]=x-y;



AP SSC Social Model 说:
Sep 19, 2022 12:38:26 AM

Social Study is most important students to all students of AP 10th Class, here we have provided the study material with solved question bank for all government and private school TM, EM, UM and HM students in chapter wise from past years old exams and we have provided the AP 10th Social Model Paper 2023 Pdf suggested by subject experts. AP SSC Social Model Paper All BSEAP 10th class regular and private course students can follow the list of chapters under SSC Social Study to practice study material with previous question bank to get a better score in summative assessment (SA) and formative assessment (FA) SA-1, SA-2, FA-1, FA-2, FA-3, FA-4 along with Assignments exams previously called Unit Test-1, Unit Test-2, Unit Test-3, Unit Test-4 and Three Months.

登录 *

loading captcha image...
or Ctrl+Enter