Shaass and Lights

题目描述

There are $n$ lights aligned in a row. These lights are numbered $1$ to $n$ from left to right. Initially some of the lights are switched on. Shaass wants to switch all the lights on. At each step he can switch a light on (this light should be switched off at that moment) if there’s at least one adjacent light which is already switched on.

He knows the initial state of lights and he’s wondering how many different ways there exist to switch all the lights on. Please find the required number of ways modulo $1000000007$ ($10^9+7$).

题意概述

有$n$盏灯排成一条直线，已知其中每一盏灯的初始状态。每次只能打开其左边一盏灯或右边一盏灯已经打开的灯。求打开所有灯的方案数。

数据范围：$1 \le n \le 1000$。

算法分析

显然，开着的灯把关着的灯分成了若干个区间。设有$k$个区间，第$i$个区间的长度为$l_i \ (0 \le l_i \le n)$，将这个区间内的灯全部打开的方案数为$s_i$。对于$s_i$满足

$$
s_i=
\begin{cases}
1, & i=1 \lor i=k \\
2^{max(l_i-1, 0)}, & otherwise
\end{cases}
$$

证明如下：

对于第$1, k$个区间，只能从区间的一端开始开灯，只有一种方案。

对于第$i \ (1 \lt i \lt k)$个区间，总共要开$l_i$次灯，除最后一次外，其他每一次开灯都可以选择从左端开还是从右端开，共有$2^{max(l_i-1, 0)}$种方案。

令$t_i=\sum_{j=1}^i l_j$，$f_i$表示打开前$i$个区间所有灯的方案数。对于$f_i$满足

$$
f_1=1, \ f_i={t_i \choose l_i}s_if_{i-1}
$$

证明如下：

打开前$(i-1)$个区间所有灯的方案数为$f_{i-1}$，打开第$i$个区间所有灯的方案数为$s_i$。如果第$i$个区间的灯都在前$(i-1)$个区间的灯之后打开，根据乘法原理，方案数为$s_if_{i-1}$。接下来就是开灯顺序的问题，相当于在打开的$t_i$盏灯中有$l_i$盏灯是属于第$i$个区间的。再次依据乘法原理，即可得到递推式。

代码

#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
long long n, m, ans, last, tot, a[1001], p[2001], c[2001][2001];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
    }
    sort(a + 1, a + m + 1);
    p[0] = p[1] = 1;
    for (int i = 2; i <= 2000; ++i) {
        p[i] = (p[i - 1] << 1) % MOD;
    }
    for (int i = 0; i <= 2000; ++i) {
        c[i][0] = c[i][i] = 1;
    }
    for (int i = 2; i <= 2000; ++i) {
        for (int j = 1; j < i; ++j) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
        }
    }
    ans = 1, last = a[1], tot = a[1] - 1;
    for (int i = 2; i <= m; ++i) {
        (ans *= p[a[i] - a[i - 1] - 1] * c[tot + a[i] - a[i - 1] - 1][tot] % MOD) %= MOD;
        tot += a[i] - a[i - 1] - 1;
    }
    (ans *= c[tot + n - a[m]][tot]) %= MOD;
    cout << ans << endl;
    return 0;
}