fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int mod =10e9+7;
  5.  
  6. int n,k,a[30];
  7. int dp[(1<<26)];
  8.  
  9. int add(int a,int b){
  10.     int res=(a+b)%mod;
  11.     return res<0?res+mod:res;
  12. }
  13.  
  14. int solve(int id, int mask){
  15.     if(id>=n) return 1;
  16.     if(dp[mask]!=-1) return dp[mask];
  17.     int cnt=0;
  18.     dp[mask]=0;
  19.     for (int i=0;i<id;i++){
  20.         if((mask>>i) & 1){
  21.             cnt++;
  22.             if(a[id]<a[i])
  23.                 dp[mask]=add(dp[mask],solve(id+1,(mask ^ (1<<i)) | (1<<id)));
  24.         }
  25.     }
  26.     if(cnt<k) dp[mask]=add(dp[mask],solve(id+1,(mask | (1<<id))));
  27.     return dp[mask];
  28. }
  29.  
  30. int main(){
  31.     cin>>n>>k;
  32.  
  33.     for(int i =0;i<n;i++) cin>>a[i];
  34.  
  35.     memset(dp,-1,sizeof dp);
  36.  
  37.     cout<<solve(0,0);
  38.  
  39.     return 0;
  40. }
Success #stdin #stdout 0.06s 277376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/bUkSWx
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!