1434. 每个人戴不同帽子的方案数

套路：枚举一个变量（或者说按顺序搜索），另一个变量根据搜索路线状态压缩+记忆化处理。

注意到帽子颜色很多，枚举每个帽子是否被选择不现实（共有种情况）。

但同样注意到人数很少，转换一下思路：状态中表示这个人是否选好了帽子，总共种情况，从开始依次枚举帽子即可。

同时结合记忆化：表示从第个帽子，状态开始选，合法的方案数。保证时间复杂度。

代码：

class Solution {
public:
	int n;
	int f[42][1111];
	const int p=1e9+7;
	vector<int>a[45];
	int dfs(int x,int zt){
		if(f[x][zt]!=-1){
			return f[x][zt];
		}
		if(x==41){
			if(zt==((1<<n)-1)){
				return f[x][zt]=1;
			}
			return f[x][zt]=0;
		}
		int res=0;
		for(int i=0;i<a[x].size();i++){
			if(!(zt&(1<<a[x][i]))){
				res+=dfs(x+1,zt|(1<<a[x][i]));
				if(res>=p) res-=p;
			}
		}
		res+=dfs(x+1,zt);
		if(res>=p) res-=p;
		f[x][zt]=res;
		return res;
	}
    int numberWays(vector<vector<int>>& hats) {
        n=hats.size();
		for(int i=0;i<n;i++){
			for(int j=0;j<hats[i].size();j++){
				a[hats[i][j]].push_back(i);
			}
		} 
		memset(f,-1,sizeof(f));
		return dfs(1,0);
    }
};