记录编号	136549	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]洪水疏导	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	3.040 s
提交时间	2014-11-03 09:54:32	内存使用	16.06 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long LL;
const int MOD=1000000007;
const int SIZEN=60,SIZEH=250,MAXK=16;
int N,K;
int H[SIZEN];
int f[SIZEN][1<<MAXK]={0};
int sum1[1<<MAXK]={0},sum2[1<<MAXK]={0};
//sum1[i]=sigma(f[s]),sum2[i]=sigma(f[s]*cnt[s]),其中s为i的子集
int cnt[1<<MAXK]={0};
int one[MAXK+10]={0};//one[i]=2^i-1
void printdig(int s){
	for(int i=0;i<K;i++) cout<<((s>>i)&1);
}
void prepare(void){
	cnt[0]=0;
	for(int i=1;i<(1<<K);i++) cnt[i]=cnt[i-lowbit(i)]+1;
	one[0]=0;
	for(int i=1;i<=K;i++) one[i]=(one[i-1]<<1)|1;
}
void work(void){
	for(int i=1;i<N;i++){
		if(H[i+1]-H[i]>K){
			printf("0\n");
			return;
		}
	}
	f[N][one[K]]=1;
	for(int i=N-1;i>=1;i--){
		memset(sum1,0,sizeof(sum1));
		memset(sum2,0,sizeof(sum2));
		int d=H[i+1]-H[i],len=K-d;//len是后边自由位的数量
		//在自由位后面的d位(K-len=d)必须是1
		for(int t=0;t<(1<<len);t++){
			int s1=(t<<d)|one[d-1];//以i为视角的表示
			int s2=t|(one[d]<<len);//以i+1为视角的表示
			f[i][s1]=f[i+1][s2];//这个比较特殊,得单独算
			sum1[s1]=(sum1[s1]+f[i+1][s2])%MOD;
			sum2[s1]=(sum2[s1]+(LL)f[i+1][s2]*cnt[s1]%MOD)%MOD;
		}
		for(int j=0;j<K;j++){//累加sum1和sum2
			for(int s=0;s<(1<<K);s++){
				if(s&(1<<j)){
					sum1[s]=(sum1[s]+sum1[s^(1<<j)])%MOD;
					sum2[s]=(sum2[s]+sum2[s^(1<<j)])%MOD;
				}
			}
		}
		for(int s=0;s<(1<<K);s++){
			LL tmp=cnt[s]*(LL)sum1[s]-sum2[s];
			tmp%=MOD;if(tmp<0) tmp+=MOD;
			f[i][s]=(f[i][s]+tmp)%MOD;
		}
	}
	printf("%d\n",f[1][one[K]]);
}
void read(void){
	scanf("%d%d",&N,&K);
	for(int i=1;i<=N;i++) scanf("%d",&H[i]);
	sort(H+1,H+1+N);
}
int main(){
	freopen("nt2012_road.in","r",stdin);
	freopen("nt2012_road.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}