2992. Number of Self-Divisible Permutations

Given an integer n, return the number of permutations of the 1-indexed array nums = [1, 2, ..., n], such that it’s self-divisible.

A 1-indexed array a of length n is self-divisible if for every 1 <= i <= n, gcd(a[i], i) == 1.

A permutation of an array is a rearrangement of the elements of that array, for example here are all of the permutations of the array [1, 2, 3]:

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

int dp[1<<13];
class Solution {
    int helper(int mask, int pos, int n) {
        if(pos == n + 1) return mask == (1<<n) - 1;
        int& res = dp[mask];
        if(res != -1) return res;
        res = 0;
        for(int i = 1; i <= n; i++) {
            if((mask >> (i-1)) & 1) continue;
            if(__gcd(i,pos) != 1) continue;
            res += helper(mask | 1ll<<(i-1), pos + 1, n);
        }
        return res;
    }
public:
    int selfDivisiblePermutationCount(int n) {
        memset(dp,-1,sizeof dp);
        return helper(0,1,n);
    }
};