题目大意：

有n盏灯，(0<=n<=1000),有m盏已经点亮，每次只能点亮与已经点亮的灯相邻的灯，求总方案数，答案对1e9+7取模

第一行：两个整数n,m表示灯的总数和已点亮的灯的数目 第二行m个数，表示已点亮的灯的编号

分析：

我们可以借助已经被点亮的灯作为分界点，找到若干个长度不为0的开区间。

对于两边都有开着的灯的区间，我们点亮它每次可以点亮最左边一盏或者最右边一盏，而最后一盏灯只有一种方法，所以点亮长度为len的区间的方案数为：2^(len-1)

特别地，对于两端的区间（一边有灯开着，一边是边界（1或者n）），只有一种方案数（顺着一路点下去）

根据乘法原理，可以先计算出ans*=2^(len2-1)2^(len-2-1)...2^(len(cnt-1)-1)注意开始的时候是i=2，最后一段是i=cnt-1；（最初最末两端算上是没有意义的）

但是由于点灯的时候可以交叉在每个区间内点灯，所以这样的ans还是少了很多。

所以我们重新这样考虑： 考虑将每个区间内考虑成颜色相同的len个球，不同区间球的颜色不同。每一个排列可以当做是一个指令，不同的合法的指令是不同的方案数。

容易知道最初的方案数为：（n-m）！我们将它处理成多重集合的排列，(n-m)!/len1!len2!...lencnt!。这样保证了每个区间内的同一种颜色的球的“单纯相对顺序”（只是这些球之间交换顺序）变化都算作是一种方案。

但是一个区间内，并不是一种方案，对于len的球数，可以有2^(len-1)种合法排列，利用乘法原理再将它们相乘，就可以得出正确的答案。

(需要：快速幂，乘方的乘法逆元） 附代码：

#include
     
      #define ll long long#define int long longusing namespace std;const int mod=1e9+7;const int N=1005;int n,m;int len[N];//区间长度;ll fac[N];//阶乘;ll ifac[N];//阶乘逆元;ll qm(int x,int y){    ll base=x;    ll ans=1;    while(y)    {        if(y&1) ans=(ans*base)%mod;        base=(base*base)%mod;        y>>=1;    }    return ans%mod;}//快速幂 int cnt;ll anss=1;int h[N];signed main(){    scanf("%lld%lld",&n,&m);    int last=0;    int x;    for(int i=1;i<=m;i++)    {scanf("%lld",&h[i]);}    sort(h+1,h+m+1);//注意，编号可能不是单调的。     len[++cnt]=h[1]-last-1;    for(int i=2;i<=m;i++)    {        if(h[i]-h[i-1]>1) len[++cnt]=h[i]-h[i-1]-1;    }    len[++cnt]=n-h[m];    for(int i=2;i<=cnt-1;i++)     anss=(anss*qm(2,len[i]-1))%mod;//先处理2^len     fac[0]=1;    ifac[0]=1;    for(int i=1;i<=n-m;i++)     fac[i]=(fac[i-1]*i)%mod;//阶乘     ifac[n-m]=qm(fac[n-m],mod-2)%mod;//费马小定理先算n-m     for(int i=n-m-1;i>=1;i--)     ifac[i]=(ifac[i+1]*(i+1))%mod;//递推算阶乘逆元     anss=(anss*fac[n-m])%mod;    for(int i=1;i<=cnt;i++)     anss=(anss*ifac[len[i]])%mod;//多重集合排列处理     printf("%lld",anss%mod);    return 0;}
     

还有一种组合数学的思想，

就是利用乘法原理，每次乘上：在每次剩余的位置放上len个数的方案数。

友链：