记录编号	168192	评测结果	AAAAAAAAATTAATTAATAA
题目名称	[国家集训队2012]洪水疏导	最终得分	75
用户昵称	天一阁	是否通过	未通过
代码语言	C++	运行时间	14.821 s
提交时间	2015-07-01 20:15:18	内存使用	29.02 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>

#define N 60
#define SL (1<<16)+10
#define LL long long
#define bit(i) (1<<(i-1))
#define c(w,i) ((w>>(i-1))&1)
#define mod 1000000007

using namespace std;

/*
f(i,t) = f'(i,t) + ∑f'(i,s)*count(t-s) (s是t的子集)
f'(i+1,t>>(a(i)-a(i-1))) += f(i,t)
*/

int n,K;
int nt[N],a[N],g[N],cnt[SL];
int f[N][SL],h[N][SL];

int add(int a,int b){
	if(a+b>=mod) return a+b-mod;
	return a+b;
}

int mul(int a,int b){
	return (int)((LL)a*(LL)b%mod);
}

int count(int S){
	int ans=0;
	for(;S;S>>=1) if(S&1) ans++;
	return ans;
}

void print(int S,int n){
	for(int i=1;i<=n;i++) printf("%d",c(S,i));
	printf("\n");
}

int main(){
	freopen("nt2012_road.in","r",stdin);
	freopen("nt2012_road.out","w",stdout);
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
//	for(int i=1;i<=n;i++) printf("%d%c",a[i],i==n?'\n':' ');
	for(int i=0;i<(1<<K);i++) cnt[i]=count(i);
	for(int i=1;i<=n;i++){
		g[i]=0;
		for(int j=i+1;a[j]-a[i]<=K && j<=n;j++)
			g[i]|=bit(a[j]-a[i]);
	}
//	for(int i=1;i<=n;i++) print(g[i],K);
	h[1][0]=1;
	for(int i=1;i<=n;i++){
		for(int t=0;t<(1<<K);t++){
			if((g[i]|t)^g[i]) continue; 
			f[i][t] = h[i][t];
			for(int s=0;s<(1<<K);s++)
				if(!((s|t)^t)){
					f[i][t] = add(f[i][t],
						mul(h[i][s],cnt[t&(~s)]) );
				}
		//	printf("f[%d][%d] = %d\n",i,t,f[i][t]);
		}
		if(i<n){
			for(int t=0;t<(1<<K);t++){
				if(!((t>>(a[i+1]-a[i]-1))&1)) continue;
				h[i+1][t>>(a[i+1]-a[i])] =
					add(h[i+1][t>>(a[i+1]-a[i])], f[i][t]);
			}
		}
	}
	printf("%d\n",f[n][g[n]]);
	return 0;
}