# 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$).

## 算法分析

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

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

## 代码

#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;
}


418 I'm a teapot