fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 1e9 + 7;
  5. const int MAX_N = 25;
  6.  
  7. int N, K, A[MAX_N];
  8. int dp[1<<MAX_N];
  9.  
  10. int main() {
  11.     cin >> N >> K;
  12.     for(int i=0; i<N; i++)
  13.         cin >> A[i];
  14.  
  15.     for(int L=(1<<N)-1; L>=0; L--) {
  16.         int num_seq = 0, highest_bit = -1, i;
  17.         for(int j=0; j<N; j++) {
  18.             if(L & 1<<j) {      // if j in L
  19.                 num_seq++;
  20.                 highest_bit = j;
  21.             }
  22.         }
  23.         if(num_seq>K)
  24.             continue;
  25.         i = highest_bit + 1;
  26.         if(i==N) {
  27.             dp[L] = 1;
  28.             continue;
  29.         }
  30.         dp[L] = 0;
  31.         for(int j=0; j<i; j++)
  32.             if(L & 1<<j)
  33.                 if(A[i] < A[j])
  34.                     dp[L] = (dp[L] + dp[L ^ 1<<j | 1<<i]) % MOD;
  35.                     // (L ^ 1<<j) removes j from L if already present
  36.                     // (L | 1<<i) adds i to L
  37.         if(num_seq<K)
  38.             dp[L] = (dp[L] + dp[L | 1<<i]) % MOD;
  39.     }
  40.  
  41.     cout << dp[0] << endl;
  42.  
  43.     return 0;
  44. }
Success #stdin #stdout 0s 147136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/jN7sp1
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!