最近跪了两场CF，rating直接回到解放前了，这场DIV2，第二题DP，我一直没贪过去，第三题，也看了，没啥想法。。。

很神的组合题。

先是亮的灯泡把暗的灯泡分成很多段，特殊考虑第一段和最后一段(如果存在)。然后中间每一段的组合方式是2^(a[i]-1)。

然后就是把n个有顺序的数，插入m个有顺序的数字(fun函数)。注意精度神马的，各种细节。。

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 #define MOD 1000000007 5 #define LL __int64 6 int Min(int a,int b) 7 { 8     return a < b ? a:b; 9 }10 LL bin[1001],c[1001][1001];11 int flag[1001],a[1001];12 LL fun(int n,int m)13 {14     int i,minz;15     LL ans = 0;16     if(n == 0||m == 0)17     return 1;18     minz = Min(m+1,n);19     for(i = 1;i <= minz;i ++)20     {21         ans = (ans + c[m+1][i]*c[n-1][i-1])%MOD;22     }23     return ans;24 }25 int main()26 {27     int i,j,n,m,temp,sum,num;28     LL ans;29     for(i = 0;i <= 1000;i ++)30     {31         c[i][0] = 1;32     }33     for(i = 1;i <= 1000;i ++)34     {35         for(j = 1;j <= 1000;j ++)36         c[i][j] = (LL)(c[i-1][j-1] + c[i-1][j])%MOD;37     }38     bin[0] = 1;39     for(i = 1;i <= 1000;i ++)40     bin[i] = (2*bin[i-1])%MOD;41     scanf("%d%d",&n,&m);42     for(i = 1;i <= m;i ++)43     {44         scanf("%d",&num);45         flag[num] = 1;46     }47     if(n == m)48     {49         printf("1\n");50         return 0;51     }52     num = 1;53     temp = 0;54     for(i = 1;i <= n;i ++)55     {56         if(flag[i] == 1)57         {58             a[num++] = temp;59             temp = 0;60         }61         else62         temp ++;63     }64     ans = fun(temp,a[1]);65     sum = temp + a[1];66     for(i = 2;i < num;i ++)67     {68         if(a[i] != 0)69         ans = (((ans*fun(sum,a[i]))%MOD)*bin[a[i]-1])%MOD;70         sum += a[i];71     }72     printf("%I64d\n",ans);73     return 0;74 }