Bitmask DP (Hamiltonian Paths)
O(2^n · n²)DP over subsets: dp[mask][v] = number of ways (or best cost) to visit exactly the vertices in mask and stand at v. Transitions extend the path by one unvisited vertex. This is the TSP pattern; it works whenever 'which elements are used' matters but their order can be compressed away. n tops out around 20 (2^20 masks); if n is 40, that is a meet-in-the-middle hint instead.
// use it on
CSES: Hamiltonian Flights ↗
Count routes visiting every city exactly once from city 1 to city n: the template with counting transitions, mod 10^9+7. Force the path to start at 0 and only count masks ending at n-1 with all bits set.
// the code
const long long MOD = 1e9 + 7;
// count Hamiltonian paths 0 -> n-1; adj[u] = list of v with edge u->v
long long count_paths(int n, vector<vector<int>>& adj) {
vector<vector<long long>> dp(1 << n, vector<long long>(n, 0));
dp[1][0] = 1; // start: only vertex 0 visited, standing at 0
for (int mask = 1; mask < (1 << n); mask++)
for (int u = 0; u < n; u++) {
if (!dp[mask][u] || !(mask >> u & 1)) continue;
for (int v : adj[u]) {
if (mask >> v & 1) continue; // already visited
dp[mask | (1 << v)][v] = (dp[mask | (1 << v)][v] + dp[mask][u]) % MOD;
}
}
return dp[(1 << n) - 1][n - 1];
}
// min-cost version (TSP): swap counting for
// dp[nm][v] = min(dp[nm][v], dp[mask][u] + cost[u][v])// more bitmask