I believe everyone will FWT and FMT.

If you don't , I recommend you to have a look at VFK Of 2015 National training team .

Let the complete set be $$U=\{1,2,\ldots,n\}$$, Suppose we care about $$f_S$$ The set in $$S$$ yes $$U$$ Subset .

Here you are. $$c_i,d_i$$, Make
$b_i=(1+c_ix^{d_i})$

seek
$g=\prod_{i}b_i$
The product of two set power series is set merging convolution （or）/ Set symmetric difference convolution （xor） One of the .

Might as well set $$d_S$$ Different from each other （ Otherwise you can use DP/ Combination number or something ）.

Make
\begin{align} a_S&=\sum_{d_i=S}c_i\\ f_S&=1+a_Sx^S \end{align}

## Violence

Do it again for each set power series FMT/FWT, And then we'll just ride them together , Switch back .

Time complexity ：$$O(n4^n)$$

It's too slow , Because it doesn't use the special condition of this problem .

## Set or convolution

For a set power series $$f$$, Definition $$f$$ The Mobius transformation of is a set power series $$\hat f$$, among
\begin{align} \hat f_S=\sum_{T\subseteq S}f_T \end{align}
In turn, , Definition $$\hat f$$ The Mobius inversion of is $$f$$, From the inclusion exclusion principle, we can get
$f_S=\sum_{T\subseteq S}{(-1)}^{|S|-|T|}\hat f_T$
I believe everyone is familiar with the above contents .

Back to the formula we asked for ：
\begin{align} \hat g_T&=\prod_S \hat{f_{S}}_T\\ &=\prod_S \sum_{K\subseteq T}f_{S,K}\\ &=\prod_{S\subseteq T}{(1+a_S)} \end{align}
It's similar to the ordinary Mobius transformation ？

Put all the $$a_S$$ add $$1$$, Change the addition of Mobius transformation to multiplication , You can get $$\hat g_T$$ 了 .

Time complexity ：$$O(n2^n)$$

## Set symmetric difference convolution

We still need to use those formulas .
\begin{align} \hat g_T&=\prod_S\hat {f_S}_T\\ &=\prod_S\sum_{K}f_{S,K}{(-1)}^{|K\cap T|}\\ &=\prod_S(1+a_S{(-1)}^{|S\cap T|}) \end{align}
This is also very similar to Walsh transformation , however $${(-1)}^{|S\cap T|}$$ Only in $$a_S$$ above , So we can't put $$a_S$$ Add $$1$$ After doing the variant Walsh transformation .

But we can maintain another $$\hat h_T=\prod_S(1-a_S{(-1)}^{|S\cap T|})$$, Take the Walsh transformation of $$-\hat g_T$$ Replacing the $$\hat h_T$$, You can do it .

Time complexity ：$$O(n2^n)$$

First pit

## A related FWT&FMT More related articles about things like

1. [ Learning notes &amp; course ] The signal , aggregate , polynomial , And various convolutional transformations (FFT,NTT,FWT,FMT)

Catalog The signal , aggregate , polynomial , And convolution transformation Convolution Convolution transformation Fourier transform and signal introduce : Signal analysis The basis of transformation : The plural The Fourier transform Discrete Fourier transform FFT With the polynomial $$n$$ The subunits are complex roots Remove the lemma ...

2. C# The reflection mechanism is used to copy the fields and properties of a class ( Copy everything from one class object to another , Instead of paying the reference address )

from:https://blog.csdn.net/poxiaohai2011/article/details/27555951 //C# The reflection mechanism is used to copy the fields and properties of a class ( Copy everything from a class object ...

3. @ summary - 2@ Bit operation convolution / Subset convolution —— FWT/FMT

Catalog @0 - Reference material @ @1 - The concept and properties of XOR convolution @ @2 - Fast Walsh transform ( Exclusive or )@ @3 - Fast inverse Walsh transform ( Exclusive or )@ @4 - And convolution . Or convolution @ @5 - Reference code implementation @ @6 - ...

4. 【 Learning notes 】fwt&amp;&amp;fmt&amp;&amp; Subset convolution

Preface :yyb Fairy blog FWT The basic idea : Turn polynomials into point valued expressions , Point values are multiplied and then inversely transformed back to obtain a specific form of convolution : The degree bounds of polynomials are $$2^n$$ In the form of ,$$A_0$$ Defined as the first half of the polynomial ( The first bit of the subscript binary ...

5. stay ASP.NET I did an experiment in the lab MVC The little thing

It's a whim before work on Friday , Yes MVC I made a few comments . Later, I just wanted to make a little thing to verify some of my own ideas and help the team clear up their ideas . The required source code is free ,3 An hour's rush is a mess , There's no good architecture , And there's no code quality , It's mainly real ...

6. [WC2018] State division ( Pressure DP+FWT/FMT)

Very naked subset inversion template problem , Put on some strange clothes . Preprocess each collection first to see if it's legal , And then make the obvious compression DP. Then we find that it can be written in the form of subset inversion , Just set the template directly . Subset inversion can be seen here . The process of subset inversion is to set more one-dimensional representative sets ...

7. 《 turn 》 Set up a BLOG How many things need to be integrated ？

This article reprints CC 1 Wordpress There are not many things that need to be done , Relatively easy , but Themes It takes a lot of effort to adjust , Sometimes it has to be changed CSS. Recommend a few Wordpress Themes Website : - http://the ...

8. Recommend a IT What is necessary for people 【 I know everything I've used , Let's make our environment better and better 】

There's something called IT People's Manual , I don't know if you've ever been useful ? But it's a pity that the old one was turned off , That website says we are IT Too many new voices and some black heart companies , But forced to shut down under pressure I'm not asking , I'm just sharing I think this kind of thing should exist ~!!! to ...

9. Post one CMemDC Code , That's a good thing , short , It's the best

Rossock Published on 2006-11-28 21:53  Click on :3941 Time   come from : original text : http://yuantao82.spaces.live.com/Blog/cns!8FC0A772D812A22 ...

## Random recommendation

1. docker compose note

https://www.youtube.com/watch?v=Uez88TWOECg It's notes based on this video . Docker Compose: Compose is a tool for defin ...

2. R System analysis of language combined with probability and statistics --- Digital features

Now there's a man , How to identify this person with this person ? Then we extract the existing features , such as , Extract their height , Its appearance , His age , Analyze these characteristics , So it's certain that , This person is this person , We will never admit our mistake . Empathy , Analyze the data , Also extract ...

3. C# The basic chapter -- object-oriented （ Classes and objects ）

1. What is the class ?   A class is a template , It is to abstract the common characteristics of the same kind of things . Class creation and description : Class is based on some specific objects ( Physical things ) To abstract out the common characteristics , And then code it . In class , Using data to represent things ...

4. SyntaxHighlighter The right way to remove the help icon in the upper right corner

Post the problem picture first : On this question . There are many posts on the Internet , There are three ways , After testing , I found that some of the methods were problematic , Some methods can solve problems , But it can lead to other mistakes . Now the explanation is as follows : The original words on the Internet : syntaxhig ...

5. IntelliJ IDEA SVN All of a sudden there was no

1. stay IDEA I can't find it in China. SVN The choice of , There is no version control tool subversion, stay setting The corresponding svn Tools , This is because we are idea Of svn Plug in svn This option is disabled terms of settlement : ...

6. pymysql solve sql Injection problem

1. SQL  Inject SQL  Injection is a very common form of network attack , It's mainly through parameters  mysql  perform  sql  Statement to perform unexpected operations . namely : Because the parameters passed in change SQL The semantics of the , It becomes some other command , So we operate the numbers ...

7. Android Typical interface design (5)—— Use SlidingMenu and DrawerLayout Achieve left and right sidebar respectively

One . Problem description The sidebar is Android Interface effect is very common in application , It can be linked with the main screen on the left or right side , It is one of the typical interface design schemes that are especially suitable for small screen features such as mobile phones , Commonly used as operation menu of application , As shown in the figure The implementation sidebar can use third-party components s ...

8. HDU5086:Revenge of Segment Tree( Regular questions ）

http://acm.hdu.edu.cn/showproblem.php?pid=5086 #include <iostream> #include <stdio.h> #i ...

9. Putty The way to build a tunnel [z]

Through the last section we learned about SSH The advantages of tunnels , But both in reality and on the Internet , Tunnels have entrances and exits , This section is based on Putty Tunnel, for example , Detailed introduction Putty The way to build a tunnel . Simulation case 1 : port , The exit is 2012 port , Tunnel building ...

10. centos6.5 Next use yum Perfect build LNMP Environmental Science (php5.6,mysql5.5,nginx1.10)

preparation Configure firewall , Turn on 80 port .3306 port No need to execute this sentence :rm -rf /etc/sysconfig/iptables Go straight to modify :vi /etc/sysconfig/iptables add to 8 ...