[BZOJ4475][JSOI2015]子集选取[推导]

题意

题目链接

分析

显然可以看成一个位数为 (n) 的二进制数然后每一位分开考虑然后求和。最后的答案是 (w^n) 的形式。

考虑一个dp。

定义状态 (f_{i}) 表示选择了长度为 (i) 的三角的方案总数。

根据题意容易得到如果 (A_{i,j}) 可以为1，那么 (A_{i-1,j} ,A_{i,j-1}) 都要是1.

所以一行当中如果存在1的话一定是一段连续的前缀。

转移： (f_i=1+sum_{j=1}^{i-1}{f_j})。枚举 (i-1) 行有多少个1，然后不确定的部分是一个大小为 (n-k+1) 的三角形，同时没有任何限制。

根据递推式可以得到答案是 (2^{nk})。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9 + 7;
int n,k;
int Pow(int a,int b){
	int res=1;
	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) res=1ll*res*a%mod;
	return res;
}
int main(){
	scanf("%d%d",&n,&k);
	printf("%d
",Pow(2,1ll*n*k%(mod-1)));	
	return 0;
}