---

題目傳送門

---

前言

再次敗在 $dp$ 手下，但是數據范圍這么小應該是可以看出是 $dp$ 的（畢竟對于其他組合數的問題數據范圍都是 $10^9$ 起步）。

---

思路

題意簡化

現有 $1,2,3,...,n?1,n$，從其所組成的 $2^n?1$ 個非空集合中選出 $m$ 個，每個集合只能選一次，求【使 $?i\in [1,n]$ 在所選集合中，出現次數均為偶數的】的選擇方案書，答案對 $10^8+7$ 取模。

明確兩點：

1. 出現 $0$ 次也算出現偶數次；
2. 一個集合中，不可能出現兩個相同的數（集合的互斥性）。

狀態設計

設 $d{p}_i$ 表示選了 $i$ 個集合的合法方案數。
注意：在之后的轉移使，我們先 只需要讓這 $i$ 個集合 滿足“每個數出現次數為偶數”的限制。

狀態轉移

限制 $1$：每個數只能出現偶數次

首先看起來題目所給的“每個數出現偶數次”的限制不太好弄，所以我們先考慮假如已經有 $i?1$ 個確定的集合，可以怎么添加一個集合，使得這 $i$ 個集合滿足這條限制。

對于一個數 $x$：

1. 假如它在前 $i?1$ 個集合中出現了奇數次，那么它一定要在最后一個集合在出現一次，這樣才能保證 $x$ 在 $i$ 個集合中總共出現了偶數次；
2. 假如它在前 $i?1$ 個集合中出現了偶數次，那么它就不可能出現在最后一個集合中，因為為了維持其出現偶數次，且每個集合不能出現相同的數，所以在最后一個集合中，其出現次數只能為 $0$。

由上述看題解分析，假如已經確定了 $i?1$ 個集合，那最后一個集合就是確定的。

先不管其他限制，就但從這條限制來看，它就有 $A_{2^n?1}^{i?1}$ 種可能（這里之所以是排列而不是組合，是因為題目讓我們求出的【所選集合方案是不顧選出集合順序的】，所以我們在最后讓答案乘以 $m!$ 的逆元就好了）。

限制 $2$：集合不能為空集

由于可能在前 $i?1$ 個集合中，每一個數都出現了偶數次，所以在最后一個集合中任何數都不能出現，即最后一個集合使空集，這樣是不合法的。

我們從容斥角度考慮轉移，看看最后一個集合為空集的有多少種可能。

把最后一個空集去除后，發現剩下的 $i?1$ 個集合正好是一個滿足【取 $i?1$ 個集合使其滿足 “每個數只能出現偶數次” 限制】的取集合方案（因為若最后一個集合為空集，那么前 $i?1$ 個集合就必定滿足 “每個數出現偶數次” 限制），這樣的情況有 $d{p}_{i?1}$ 種。

所以在總的選擇方案中減去 $d{p}_{i?1}$ 就行。

限制 $3$：每個集合只能選一次，即不能出現兩個相同的集合

由于前 $i?1$ 個集合一定互不相同（因為我們是從 $n$ 個數組成的 $2^n?1$ 個互不相同的集合中選出的），所以只考慮【第 $i$ 個集合與前 $i?1$ 個集合中】有一個相同的方案。

先明確一點：假如 $i$ 與前 $i?1$ 個集合中的某個相同（假設是第 $j$ 個集合），那么決定第 $i$ 個集合構造方法的就是集合 $j$。

因此，我們如果去除集合 $i,j$，那么剩下的 $i?2$ 個集合一定能形成一組滿足【取 $i?2$ 個集合使其滿足 “每個數只能出現偶數次” 限制】的取集合方案。因為兩個集合中的數相同，因此刪除這兩個集合的話，集合中的數也是成對被刪除的，因此能構成。這樣的 $i?2$ 個集合共有 $d{p}_{i?2}$ 種。

又因為 $j$ 有 $i?1$ 種取法，集合 $i$ 有 $2^n?1?(i?2)$ 種（即在所有的 $2^n?1$ 個集合中，去除【已有的 $i?2$ 個集合】剩下的之中，再選一個），剩下的 $i?2$ 個集合共有 $d{p}_{i?2}$ 種，所以這個非法方案數是 $(i?1)\times (2^n?1?(i?2))\times d{p}_{i?2}$。

綜上，轉移方程就是：
$$d{p}_i=A_{2^n?1}^{i?1}?d{p}_{i?1}?(i?1)\times (2^n?1?(i?2))\times d{p}_{i?2}$$

邊界條件

首先是 $d{p}_1=0$：因為只選一個非空的不重集合就讓每個數出現偶數次顯然是不可能的；
其次是 $d{p}_2=0$：因為要在前兩個集合中，就使每個數出現偶數次，要么得是兩個空集，要么兩個集合就得一樣，這樣顯然也是不合法的。

答案

是 $d{p}_m\times inv(m!)$，因為題目要求出的集合是不顧 $m$ 個集合順序的，而在計算時我們有考慮了其順序，所以要除去 $m!$。

復雜度

時間空間均為$O(m)$。

---

代碼

#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 1e6 + 7;
const int mod  = 1e8 + 7;int n, m;
int facm = 1, invm;
int tot;
int qpow(int x, int y) {int res = 1;for (; y; y >>= 1, x = x * x % mod)if (y & 1) res = res * x % mod;return res;
}int dp[maxn], A[maxn];
signed main() {scanf("%lld%lld", &n, &m);for (int i = 1; i <= m; ++i)facm = facm * i % mod;invm = qpow(facm, mod - 2);tot = (qpow(2, n) - 1 + mod) % mod;A[0] = 1;for (int i = 1; i <= m; ++i)A[i] = A[i - 1] * (tot - i + 1) % mod;dp[1] = dp[2] = 0;for (int i = 3; i <= m; ++i)dp[i] = ((A[i - 1] - dp[i - 1] - (tot - i + 2) * (i - 1) % mod * dp[i - 2] % mod) % mod + mod) % mod;printf("%lld\n", dp[m] * invm % mod);return 0;
}