# 位元dp與基礎捲積
## 位元dp
先直接看題目
### [Elevator Rides](https://cses.fi/problemset/task/1653/)
有$n$個人要搭一部承重為$x$的電梯，問最少需要幾趟?
* $n\leq 20$
* $x\leq 10^9$

發現到$n$很小，所以應該會是$O(2^n)$或$O(n2^n)$之類的複雜度，不難想到，可能會和窮舉子集合有關，不意外就是dp。

#### 定義狀態:
$dp[i]$ : $i$這個集合的人都已經搭完的答案。
$last[i]$ : $i$ 這個集合的人都已經搭完，最後一趟的載重。

#### 以數字表示集合:
將在集合內的人以$1$表示，反之則為$0$。
例如總共若有六個人，則$\{ 2, 3, 5\}\Rightarrow 101100_{(2)}=44_{(10)}$
即若集合為$A$，則代表此集合的數字即為$\sum_{i\in A}2^i$。

#### 狀態轉移:
窮舉集合$i$，再窮舉轉移點，例如$101100$的轉移點有可能是$001100$、$100100$或$101000$。用轉移點的$last$判斷以此點轉移是否需要開一趟新的，$dp$值越小越好，並且滿足此條件下$last$值越小越好。
複雜度$O(n2^n)$

:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x;
    cin>>n>>x;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    vector<int> dp(1<<n),last(1<<n);
    dp[0]=1;
    last[0]=0;
    for(int i=1;i<=1<<n;i++){//窮舉子集合
        dp[i]=INT_MAX;
        last[i]=INT_MAX;
        for(int j=0;j<n;j++){//窮舉轉移點
            if(i&(1<<j)){
                int a=i-(1<<j);//轉移點
                if(last[a]+v[j]<=x){
                    if(dp[a]<dp[i]||(dp[a]==dp[i]&&last[a]+v[j]<last[i])){
                        dp[i]=dp[a];
                        last[i]=last[a]+v[j];
                    }
                }
                else {
                    if(dp[a]+1<dp[i]||(dp[a]+1==dp[i]&&v[j]<last[i])){
                        dp[i]=dp[a]+1;
                        last[i]=v[j];
                    }
                }

            }
        }
    }
    cout<<dp[(1<<n)-1]<<endl;
    return 0;
}

:::
### [貨郎問題](https://judge.tcirc.tw/ShowProblem?problemid=d089)
有$n$個點，現給所有點對間的最短距離，求一個環通過所有點的最短距離
* $n\leq 17$

錯誤解法:枚舉所有可能的排列，複雜度$O(n!)$

#### 定義狀態:
對於兩個相同起點的不同的路徑(尚未走完)，如果它們走過的點集合一樣，最後停留的點也一樣，那麼這兩條路徑就只需要一條比較短的就可以了，例如$P=\{ 0, 1, 3, 7, 4\}$與$Q=\{0, 7, 3, 1, 4\}$，他們經過的點集合都是$\{ 0, 1, 3, 4, 7\}$而最後停留點都是 4，所以並不需要都留下來，也就是說，我們需要考慮的狀態是所有的$(S,p)$，其中$S$是所有的子集合，而$p$是所有可能的點，

#### 狀態轉移:
枚舉$S$、$p$、轉移點。
複雜度$O(n^2 2^n)$

### 題目
[Hamiltonian Flights](https://cses.fi/problemset/task/1690)
[Team Building](https://codeforces.com/contest/1316/problem/E)
[Matching](https://atcoder.jp/contests/dp/tasks/dp_o?lang=en)
## 捲積
基本上考試比賽應該都用不到，除非你超電

### [捲積](https://zh.wikipedia.org/zh-tw/%E5%8D%B7%E7%A7%AF)(convolution)的基本認識
$$\int^{\infty}_{-\infty} f(\tau)g(t-\tau)d\tau$$
一個有趣的理解方式:
![](https://hackmd.io/_uploads/B1LHcvuUn.png
)
$f(x)$為每個時間點攝取的食物，$g(x)$為每單位食物隨時間消化後在胃中剩餘的量。捲積的結果為$t$時胃中剩下的食物量。
也可以理解成把其中一個函數對某個點左右翻轉並把兩函數的值相乘。

如果把定義離散，然後把函式用陣列表示:
$$C[k]=\sum_{i+j=k} A[i]B[j]$$
可以利用[快速傅立葉變換](https://zh.wikipedia.org/zh-tw/%E5%BF%AB%E9%80%9F%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2)在$O(n\log n)$時間內算出。我還不會。

### 捲積的應用
令$A[i]$為$A(x)$這個多項式$x^i$項的係數，等我哪一天學會了再說。

$$
\\C[k]=\sum_{i+j=k} A[i]B[j]\\
\begin{aligned}
\\C(x)&=\sum_{k=0}^{n-1}\sum_{i+j=k} A[i]B[j]x^k
\\&=A(x)B(x)
\end{aligned}
$$
這表示我們可以在$O(n\log n)$(若陣列長度為$n$)的時間內算出多項式的乘法。

基本上就是應用FTT或NTT來加速。

### OR convolution
[OR Convolution For Common People](https://codeforces.com/blog/entry/115438)
顧名思義，就是把$+$換成$\lor$(bitwise or)。
以下設陣列大小為$2^n$。

$$C[i]=\sum_{j\lor k=i} A[j]B[k]$$

把數字換成集合:

$$C[i] = \sum_{j \cup k = i} A[j] B[k]$$

把條件放寬:
$$C^\prime[i] = \sum_{(j \cup k) \subseteq i} A[j] B[k]$$
也就是說，原本$j$和$k$聯集起來必須要是$i$，但現在聯集起來只要是$i$的子集合就好，做這件事情可以使$C^\prime[i]$為所有$i$的子集合的$C$相加，即$C^\prime[i] = \sum_{j \subseteq i} C[j]$，

接著繼續簡化，若$(j \cup k) \subseteq i$，則$(j \subseteq i) \land (k \subseteq i)$:

$$C^\prime[i] = \sum_{(j \subseteq i) \land (k \subseteq i)} A[j] B[k]$$

然後發現結果就是$A$中挑一個，$B$中挑一個相乘，用一些分配律的想法就可以變成:
$$C^\prime[i] = \sum_{(j \subseteq i) \land (k \subseteq i)} A[j] B[k] = (\sum_{j \subseteq i} A[j]) (\sum_{k \subseteq i} B[k])
$$
令$A^{\prime}[i]=\sum_{j \subseteq i} A[j]$
所以問題就變成:求$A$中求索引值為$i$的子集合的和。
就相當於前面位元dp的問題。

#### 定義狀態:
令$dp[i][j]$為考慮前$i$個bit中，$A$中索引值為$j$的子集合的和。

#### 狀態轉移:

可以這麼理解:
假設要算101110的答案，子集合可以分為第六位是1和第六位是0，若第六位是0，即為dp[5][001110] (101110-100000)，剩下的就是第六位是1的子集合，而這情形也可以分為第四位是否為1，若為0，則為dp[3][100110] (101110-001000)，以此類推。
時間複雜度$O(n2^n)$，空間複雜度$O(n2^n)$。

以$111$為例，
$$
\begin{aligned}
\\dp[3][111]&=A[111]+A[110]+(A[100]+A[101])+(A[000]+A[001]+A[010]+A[011])
\\&=dp[0][111]+dp[0][110]+dp[1][101]+dp[2][011]
\end{aligned}
$$

以$101$為例，
$$
\begin{aligned}
\\dp[3][101]&=A[101]+A[100]+(A[000]+A[001])
\\&=dp[0][101]+dp[0][100]+dp[2][001]
\end{aligned}
$$

dp[0]=A;
for(int i=1;i<=n;i++){
    for(int j=0;j<1<<n;j++){
        dp[i][j]=dp[i-1][j];
        if(j>>(i-1)&1){
            dp[i][j]+=dp[i-1][j-1<<(i-1)];
        }
    }
}

想一想發現又可以滾動優化，把空間複雜度壓為$O(2^n)$;

for (int i = 0; i < n; i++) {
  for (int j = 0; j < (1 << n); j++) {
    if ((j >> i) & 1) {
      A[j] += A[j - (1 << i)];
      B[j] += B[j - (1 << i)];
    }
  }
}

最後$C^{\prime}[i]$即為$A^{\prime}[i]B^{\prime}[i]$。

for (int i = 0; i < (1 << n); i++) {
  C[i] = A[i] * B[i];
}

#### 處理$C$
成功算出$C_{\prime}$了，接下來再把它還原為$C$就好了。

回顧一下:
$$C^{\prime}[i] = \sum_{j \subseteq i} C[j]$$

有沒有發現和這條一模一樣:
$$A^{\prime}[i]=\sum_{j \subseteq i} A[j]$$

唯一不同的是剛剛是已知$A[i]$要算$A^{\prime}[i]$，而現在是已知$C^{\prime}[i]$要算$C[i]$。
該怎麼做呢 沒錯就是把code全部倒著做。

for (int i = n - 1; i >= 0; i--) {
  for (int j = (1 << n) - 1; j >= 0; j--) {
    if ((j >> i) & 1) {
      C[j] -= C[j - (1 << i)];
    }
  }
}

#### 應用
這個方法也可以用在And convolution。