//何も考えずに順列を生成する //ただし、使用した数字の組み合わせ, 最後に使った数字, A[i] > A[i+1]が既に起こったかどうか、が同じならその後の並べ方も同じなので、状態をまとめる。 //ビットDP, 0~N-1を並び替えるという問題に置き換えると実装が楽。 //(どんな順列が条件を満たすかを考えるとややこしいので、実際に順列を作ってみて考える) #include using namespace std; int n, k; int dp[1 << 20][20][2]; int dfs(int rem, int last, int isReversed) { if (rem == 0) return isReversed; if (dp[rem][last][isReversed] != -1) return dp[rem][last][isReversed]; int ret = 0; for (int i = 0; i < n; i++) { //次の数字を全て試す if ((rem >> i) % 2 == 0) continue; //既に使っているのでNG if (isReversed) { if (last > i) continue; //条件を満たさなくなるのでNG ret += dfs(rem - (1 << i), i, isReversed); } else { ret += dfs(rem - (1 << i), i, (last > i)); } } return (dp[rem][last][isReversed] = ret); } int main() { cin >> n >> k; k--; //0-indexedにする for (int i = 0; i < (1 << n); i++) for (int j = 0; j < n; j++) for (int k = 0; k < 2; k++) dp[i][j][k] = -1; cout << dfs((1 << n) - 1 - (1 << k), k, 0) << endl; return 0; }