人生第一道 Sum over Subsets DP(SOSDP)。
SOSDP 顾名思义，解决的是求 f(T)=\sum\limits_{S \subset T}g(S) 的问题。
首先需要学会最简单的子集枚举。
for (int m = 0; m < (1 << n); ++m)
for (int s = m; s; s = (s - 1) & m)
第一层遍历 T，第二层遍历 S。s \gets (s-1) \land m 相当于把找到 s 的最后一个 1 并取反，所以这样一定可以降序遍历 T 的所有子集。由于最终遍历时每一位只可能出现 m 为 1 且 s 为 1，m 为 1 且 s 为 0，m 为 0 且 s 为 0 三种情况所以复杂度是 O(3^n)。
实际上对于一个状态 i，可以定义 sum_{i,j} 表示只可以修改 i 的前 j 位且是 i 的子集的所有 f_i 的和。
那么
同时，
$sum_{i,j} \gets sum_{i,j-1}+[\text{the j-th postion of i is 1}]sum_{i \oplus (1<<j),j} $。
且有初始化，
$sum_{i,1} \gets g_i+[\text{the first position of i is 1}]sum_{i\oplus 1}$。
这样我们可以得到 $O(n\times 2^n)$ 的算法解决这一问题。
回到这题，可以发现，对于一道题 $i$，每个验题人给他的评价 H(1),E(0) 可以按顺序写成长度为 $m$ 的 01 串。按照这一标准，可以将 $n$ 到题目分为 $2^m$ 组。设这组共有 $k$ 个题目，组内的排列顺序显然任意，单独一组（必须取）的方案数就是 $T(k)=A_k^1+A_k^2+ \dots + A_k^k$，可以直接预处理。组间顺序得先放子集，再放自己。设 $dp_i$ 表示以第 $i$ 组为结尾的方案数，那么 $dp_i \gets ((\sum_{j \subset i} dp_j)+ 1) \times T(|i|)$，$|i|$ 表示第 $i$ 组有多少题。看到了子集求和，可以套用上面 SOSDP 的办法，类似定义 $sumdp$。这道题就解决了。
直接枚举子集的 $O(3^n)$ CODE(60pts):
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
const int N=1e5+5,mod=1e9+7,M=20;
int n,m;
ll A[N],dp[1<<M];
int busket[1<<M];
string s[25];
int f(int x){
bitset <20> bs;
for(int i=0;i<m;++i){
bs[i]=(s[i+1][x]=='E' ? 0 : 1);
}
int k=bs.to_ullong();
return k;
}
void init(){
A[1]=1;
for(int i=2;i<=n;++i){
A[i]=(A[i-1]*i%mod+i)%mod;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;++i){
cin>>s[i];
s[i]=" "+s[i];
}
for(int i=1;i<=n;++i){
busket[f(i)]++;
}
init();
ll ans=A[busket[0]];
dp[0]=A[busket[0]];
for(int i=1;i<(1<<m);++i){
i128 sum=0;
for(int j=i;;j=(j-1)&i){
sum=(sum+dp[j])%mod;
if(j==0) break;
}
dp[i]=(sum*A[busket[i]]+A[busket[i]])%mod;
(ans+=dp[i])%=mod;
}
cout<<ans;
return 0;
}
```
SOSDP $O(n \times 2^n)$ CODE(100pts):
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
const int N=1e5+5,mod=1e9+7,M=20;
int n,m;
ll A[N],dp[1<<M],sdp[1<<M][M+5];
int busket[1<<M];
string s[25];
int f(int x){
bitset <20> bs;
for(int i=0;i<m;++i){
bs[i]=(s[i+1][x]=='E' ? 0 : 1);
}
int k=bs.to_ullong();
return k;
}
void init(){
A[1]=1;
for(int i=2;i<=n;++i){
A[i]=(A[i-1]*i%mod+i)%mod;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;++i){
cin>>s[i];
s[i]=" "+s[i];
}
for(int i=1;i<=n;++i){
busket[f(i)]++;
}
init();
ll ans=A[busket[0]];
dp[0]=A[busket[0]];
for(int i=1;i<=m;++i)
sdp[0][i]=dp[0];
for(int i=1;i<(1<<m);++i){
i128 sum=0;
for(int j=1;j<=m;++j){
if(i&(1<<(j-1))){
int pre=i^(1<<(j-1));
sum+=sdp[pre][j];
sum%=mod;
}
}
dp[i]=(sum+1)*A[busket[i]];
dp[i]%=mod;
(ans+=dp[i])%=mod;
sdp[i][1]=dp[i];
if(i&1) (sdp[i][1]+=sdp[i^1][1])%=mod;
for(int j=2;j<=m;++j){
sdp[i][j]+=sdp[i][j-1];
if(i&(1<<(j-1))){
int pre=i^(1<<(j-1));
sdp[i][j]+=sdp[pre][j];
sdp[i][j]%=mod;
}
}
}
cout<<ans;
return 0;
}
```
一些后话：SOSDP 好像就是快速莫比乌斯变化（FMT），~~可由于 FMT 过于高深我不会~~，所以就不涉及。