很明显的递推题，但是高精度。
解法
相信大家都对九连环的游戏有所了解。如果不拆除前面的环，那后面的环也就不能拆除。有依赖关系。
考虑设置状态。
题中要求所有灯全部熄灭所用的步数，所以这里设置状态 $f$，$f_i$ 表示前 $i$ 盏灯全部熄灭所用的最少步数。由于第 $i$ 盏灯可以被操作的前提是前 $i-1$ 盏灯满足一定条件，所以只能从左到右顺序操作。现在考虑如何转移。
如果第 $i$ 盏灯本来就是灭的。那这个位置不用操作，$f_i = f_{i-1}$。
如果第 $i$ 盏灯本来是亮的，那这个位置需要操作。此时已经处理了前 $i-1$ 盏灯的情况。这里分两种情况讨论。
为了辅助这个过程，我们再设一个状态 $g$，$g_i$ 表示在前 $i$ 盏灯全部熄灭的情况下点亮第 $i$ 盏灯所用的最少步数，这里等价于前 $i-1$ 盏灯全部熄灭、第 $i$ 盏灯点亮的情况下使前 $i$ 盏灯全部熄灭所用的最少步数。题中说编号为 $1$ 的灯可以随意开或关，所以 $g_1 = 1$。考虑 $g_2$。$g_2$ 即为开 $1$，开 $2$，关 $1$ 的最少步数，即为 $g_1 \times 2 + 1$。考虑 $g_i$，即为开 $i-1$，开 $i$，关 $i-1$ 的最少步数，即为 $g_i-1 \times 2 + 1$。利用数学归纳法：
\[\begin{aligned} &g_1 = 1 = 2^1 - 1 \\ &g_2 = g_1 \times 2 + 1 = (2^1 - 1) \times 2 + 1 = 2^1 + 1 = 2^2 -1 \\ &g_3 = g_2 \times 2 + 1 = (2^2 -1) \times 2 +1 = 2^3 - 2 + 1 = 2^3 - 1 \\ &g_i = g_{i-1} \times 2 + 1 = (2^{i-1} - 1) \times 2 + 1 = 2^i - 2 + 1 =2^i - 1\end{aligned}\]得出结论：$g_i = 2^i - 1$。
- 如果第 $i-1$ 盏灯本来是亮的。则 $f_i = g_{i-1} - f_{i-1} + 1 + g_{i-1} = g_i - f_{i-1}$。
- 如果第 $i-1$ 盏灯本来是熄灭的的。则 $f_i = g_{i-1} - f_{i-2} + 1 + g_{i-1} = g_{i-1} - f_{i-2} + 1 + g{i-1} = g_i - f_{i-2} = g_{i} - f_{i-1}$。
综上，$f_i = \begin{cases}f_{i-1}&a_i = 0 \ g_i - f_{i-1}&a_i = 1\end{cases}$。
高精度略。
代码
#include<bits/stdc++.h>
template <typename T>
inline void swap(T &x,T &y)
{
T tmp=x;
x=y,y=tmp;
}
class high_accuracy
{
private:
int len,a[5000];
public:
inline int &operator[](const int &x)
{
return a[x];
}
inline int size()
{
return len;
}
inline high_accuracy()
{
len=0,a[0]=a[1]=a[2]=0;
}
inline void init(__int128 x)
{
len=0;
if(x==0) len=1,a[1]=0;
while(x) a[++len]=x%10,x/=10;
}
inline void deal(int l)
{
for(int i=1;i<=l;i++)
{
while(a[i]<0) a[i+1]--,a[i]+=10;
a[i+1]+=a[i]/10,a[i]%=10;
}
len=l;
while(!a[len]) len--;
}
inline void print()
{
for(int i=std::max(len,1);i;i--) std::cout<<a[i];
std::cout<<"\n";
}
inline high_accuracy operator+(high_accuracy rhs)
{
high_accuracy ret;
int le=std::max(len,rhs.size());
for(int i=1;i<=le+3;i++) ret[i]=0;
for(int i=1;i<=le;i++) ret[i]+=a[i]+rhs[i];
ret.deal(le+2);
return ret;
}
inline high_accuracy operator-(high_accuracy rhs) // 适用于 *this 比 rhs 大的情况
{
high_accuracy ret;
int le=std::max(len,rhs.size());
for(int i=1;i<=le+3;i++) ret[i]=0;
for(int i=1;i<=le;i++) ret[i]+=a[i]-rhs[i];
ret.deal(le+2);
return ret;
}
inline high_accuracy operator*(high_accuracy rhs)
{
high_accuracy ret;
for(int i=1;i<=len+rhs.size()+5;i++) ret[i]=0;
for(int i=1;i<=len;i++) for(int j=1;j<=rhs.size();j++) ret[i+j-1]+=a[i]*rhs[j];
ret.deal(len+rhs.size()+5);
return ret;
}
};
high_accuracy f[1010],pw[1010];
int n,a[1010];
int main()
{
std::cin>>n,pw[0].init(1),pw[1].init(2),f[0].init(0);
for(int i=1;i<=n;i++) std::cin>>a[i];
for(int i=2;i<=n;i++) pw[i]=pw[i-1]*pw[1];
if(a[1]) f[1].init(1);
for(int i=2;i<=n;i++)
if(a[i]) f[i]=pw[i]-pw[0]-f[i-1];
else f[i]=f[i-1];
f[n].print();
return 0;
}
