CF294C Shaass and Lights

对于给定的 \(m\) 个点，将整个序列分为了 \(m+1\) 段，我们可以先将每一段看作同一个类型，同一个类型间不同的顺序看作同一种。那么显然，答案即为可重集的排列数。

设 \(\{S=n_1 \cdot a_1,n_2\cdot a_2,...,n_k \cdot a_k \}\) 表示由 \(n_i\) 个 \(a_i\) 组成的集合。那么此集合的排列数为 \(\dfrac{(\sum\limits_{i=1}^n n_i)!}{\prod\limits_{i=1}^n n_i!}\)。

再来看每一个相同类型的内部方案数。显然，对于非最左和最右的一段，每次我可以选择左右最后选择的两个端点的相邻点，设该相同类型的长度为 \(len\)，则方案数为 \(2^{len-1}\)。对前面的方案数相乘即可。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define R(i, l, r) for (int i = (l); i <= (r); ++i)
#define int ll
const int N = 2000 + 5, P = 1e9 + 7;
int n, m, ans = 1;
int a[N], pw[N], jc[N];
int qpow(int a, int b)
{
    int res = 1, base = a;
    while (b)
    {
        if (b & 1) res = res * base % P;
        base = base * base % P;
        b >>= 1;
    }
    return res;
}
signed main()
{
    cin >> n >> m;
    pw[0] = jc[0] = 1;
    R(i, 1, n) pw[i] = pw[i - 1] * 2 % P, jc[i] = jc[i - 1] * i % P;
    // 将每个段看成同一种类型 方案即为可重集排列数
    // 再单独看每一个段的方案数 只需要看中间段，每次有两种选择
    R(i, 1, m) cin >> a[i];
    sort(a + 1, a + m + 1);
    int t = n - m;
    R(i, 1, t) (ans *= i) %= P;
    ans *= qpow(jc[a[1] - 1], P - 2); ans %= P;
    ans *= qpow(jc[n - a[m]], P - 2); ans %= P;
    R(i, 2, m)
    {
        int len = a[i] - a[i - 1] - 1;
        if (len) (ans *= pw[len - 1]) %= P;
        (ans *= qpow(jc[len], P - 2)) %= P;
    }
    cout << ans << endl;
    return 0;
}