問題
http://yukicoder.me/problems/no/411
正の整数 N, K がある。
1~Nが1つずつあるN個の数列はN!通りあるが、その中で以下の条件を満たす組合せを数える
- 数列の先頭がK
- 数列について Ai > Ai+1 となるiがただ1つだけある
2 <= N <= 20
1 <= K <= N
考察
1. 最大20なのでbit使う感がある
2. 全探索より計算から求める方法から考え始めてしまった
3. 解説は全探索になってます
4. 計算から求める方法では場合分けの必要があります
5. 今回の問題では昇順数列を2つくっつける
6. 片方の昇順数列が決まればもう片方も一意に決まるので、片方だけ全列挙する方針で考える
7. K != 1のとき
8. 2番目の昇順数列は1から始まる
9. 1番目の昇順数列はK以上の要素のみで構成される
10. Kより大きい数は N - K個 存在するので、この数を選択する組合せは 2^(N - K) 通り
11. K == 1のとき
12. K != 1のとき同様、組合せは 2^(N - K) 通りかなという感じですが、ちょっと違う
13. 1番目の昇順数列が公差1の等差数列になってしまうと、2番目の昇順数列が作れないので、そうなる N 通りを除外する
14. これで答え
実装
http://yukicoder.me/submissions/110378
typedef long long ll; ll modpow(ll a, ll n) { if (a == 0) return 0; ll r = 1; while (n) r = r*((n % 2) ? a : 1), a = a*a, n >>= 1; return r; } //----------------------------------------------------------------- int main() { int N, K; while (cin >> N >> K) { if (K == 1) cout << modpow(2, N - 1) - N << endl; else cout << modpow(2, N - K) << endl; } }