LeetCode2741.特别的排列 状压

暴力枚举的话是n！

考虑状压DP，其实就是用二进制表示状态 再进行暴力 同时加一个记忆化就好了

这里有常用技巧：

全集（1<<n）-1

增加某个元素 x  |  (1<<i)

删除某个元素 x & ~(1<<i)

const int N = 15;
int dp[1<<N][N];
vector<int>nums1;
int mod = 1e9+7;
int n;int dfs(int u,int id){if(!u)return 1;if(~dp[u][id])return dp[u][id];int res = 0;for(int i=0;i<n;i++){if((u>>i&1)&&(nums1[id]%nums1[i]==0||nums1[i]%nums1[id]==0))res  = (res + dfs(u&~(1<<i),i))%mod;}res%=mod;return dp[u][id] = res;}class Solution {
public:int specialPerm(vector<int>& nums) {memset(dp,-1,sizeof dp);n = nums.size();nums1 = nums;nums1.push_back(1);return dfs((1<<n)-1,n);}
};