原题链接
考察:组合数学
思路:
我们不必模拟每次具体去掉什么.因为去掉的蜡烛只能在熄灭的蜡烛左右俩侧.对于区间\(2\),每次在左右端点选一个去掉,方法数是\(2^{8-4-1-1}\).但是区间1,3是特殊的,因为只有一种方法.
计算完区间内部的方法后,就是计算区间之间的方法数.这里不能用插空法.是先有\(n-m\)个位置,将位置填满的计算方法.
Code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1010,M = 1000000007;
int nums[N],n,m,C[N][N];
void init()
{
for(int i=0;i<N;i++)
for(int j=0;j<=i;j++)
if(!j) C[i][j] = 1;
else C[i][j] = ((LL)C[i-1][j-1]+C[i-1][j])%M;
}
int qsm(int a,int k,int m)
{
if(k<0) return 1;
int res = 1;
while(k)
{
if(k&1) res = (LL)res*a%m;
a = (LL)a*a%m;
k>>=1;
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
init();
int res = 1,now = n-m;
if(n==m) {puts("1");return 0;}
for(int i=1;i<=m;i++) scanf("%d",&nums[i]);
sort(nums+1,nums+m+1);
for(int i=2;i<=m;i++)
{
int len = nums[i]-nums[i-1]-1;
res = (LL)res*qsm(2,len-1,M)%M;
}
nums[m+1] = n+1;
for(int i=1;i<=m+1;i++)
{
res = (LL)res*C[now][nums[i]-nums[i-1]-1]%M;
now-=nums[i]-nums[i-1]-1;
}
printf("%d\n",res);
return 0;
}