所求即为选择的区间恰好包含所有 \(a_i = 2\) 的位置的方案数。
设所有 \(a_i = 2\) 的位置 \(i\) 组成集合 \(S\)，考虑容斥被选中的位置是 \(S\) 的子集的方案数 \(g(S)\)。
设 \(T\) 为 \(S\) 的子集，\(T\) 的贡献 \(f(T)\) 为：选中的位置都在 \(T\) 的子集中的方案数乘容斥系数 \((-1)^{|S| - |T|}\)。
将所有 \(i \in T\) 视为 \(a_i = 0\)（可选可不选）；将所有 \(i \in U - T\) 视为 \(a_i = 1\)（必须不选）。\(f(T)\) 可重新表述为不包含 \(1\) 的区间的数量的 \(m\) 次方（一个区间允许多次选，方案有序）。
只需求满足条件的区间数量，设所有被视为 \(a_i = 1\) 的位置 \(i\) 依次组成长为 \(m\) 的数列 \(b_1, b_2, \cdots b_m\)，则满足条件的区间数量为
\[\sum\limits_{i = 2}^m \frac 1 2 (b_i - b_{i - 1}) (b_i - b_{i - 1} - 1) \]考虑 DP，发现答案只与 \(b\) 的上一项有关，设 \(dp_{i, j}\) 表示 \(i\) 被视为 \(a_i = 1\)，区间数量为 \(j\) 的方案数。（为了方便初始化和统计答案，规定 \(a_0 = a_{n + 1} = 1\)）
转移
\[dp_{k, j + w} = \sum\limits_{i = 0}^{k - 1} c_i \cdot dp_{i, j} \]其中 \(c_i\) 是容斥系数，\(w\) 是权值。
发现容斥系数的指数实际上是有多少个 \(a_i = 2\) 被视为 \(a_i = 1\)，所以
\[c_i = \begin{cases} 1, &a_i = 1, \\ -1, &a_i = 2, \\ 0, &\text{otherwise}. \end{cases} \]该式中 \(a_i\) 是原数列中的 \(a_i\)。
\[w = \frac 1 2 (k - i) (k - i - 1) \]边界
\[dp_{0, 0} = 1 \]答案
\[\sum\limits_{x = 1}^{\frac 1 2 n (n + 1)} dp_{n + 1, x} \cdot x^m \]#include <iostream>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
static inline int qpow(int a, int b) {
int ret = 1;
while (b) {
if (b & 1)
ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}
int n, m;
int a[105];
int dp[105][10005];
static inline void solve() {
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 0; i <= n + 1; ++i) {
int mx = n * (n + 1) / 2;
for (int j = 0; j <= mx; ++j)
dp[i][j] = 0;
}
a[n + 1] = 1;
dp[0][0] = 1;
for (int i = 0; i <= n; ++i) {
int mx = i * (i + 1) / 2;
for (int j = 0; j <= mx; ++j) {
for (int k = i + 1; k <= n + 1; ++k) {
int w = (k - i) * (k - i - 1) / 2;
if (a[k] == 1) {
dp[k][j + w] = (dp[k][j + w] + dp[i][j]) % mod;
break;
} else if (a[k] == 2) {
dp[k][j + w] = (dp[k][j + w] - dp[i][j] + mod) % mod;
}
}
}
}
int mx = n * (n + 1) / 2;
int ans = 0;
for (int i = 0; i <= mx; ++i)
ans = (ans + dp[n + 1][i] * qpow(i, m) % mod) % mod;
cout << ans << endl;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("P9891.in", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
return 0;
}