fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. int exp( int bs, int po)
  7.  {
  8.    int ans = 1 ;
  9.    while(po)
  10.     {
  11.       if(po&1) ans*=bs;
  12.       bs*=bs;
  13.       po>>=1;
  14.     }
  15.    return ans;
  16.  }
  17.  
  18. ll m , n ,  k ;
  19. int dp[32800][51][51];
  20.  
  21. ll rec(int vtx , vector<vector<int> > &g,ll sum ,ll idx,vector<int>&ct)
  22.  {
  23.    ll tp = 0;
  24.  
  25.      if(sum > k || idx > n)
  26.        return 0 ;
  27.  
  28.      if( idx == n && sum == k )
  29.           tp = 1 ;
  30.  
  31.       if(dp[vtx][sum][idx]!=-1)
  32.          { 
  33.          return dp[vtx][sum][idx];}
  34.  
  35.  
  36.  
  37.      for( size_t i = 0 ; i<g[vtx].size() ; i ++ )
  38.         {
  39.              int vt = g[vtx][i] ;
  40.              tp += rec( vt , g , sum + ct[ vt ] , idx + 1 ,ct);
  41.  
  42.         }
  43.  
  44.  dp[vtx][sum][idx]  = tp;
  45.        return tp;
  46.  }
  47.  
  48. int main()
  49.  
  50. {
  51.   ios::sync_with_stdio(0);
  52.   cin.tie(0);
  53.  
  54.   cin>>m>>n>>k;
  55.  
  56.   vector<int>vst; // To store valid states
  57.   vector<vector<int> > g(32800); // to store paths form one valid state to another
  58.   vector<int>ct(32800); // to store number of 1s in ach valid state  
  59.  
  60.   //vector<int>idx(32800);
  61.  
  62. // finding the valid states 
  63.   for( int i =  0 ; i < exp(2,m) ; i ++ )
  64.     for( int j = 1; j <32 ; j ++ )
  65.       {
  66.            if( (1<<j)&i  && (1<<(j-1))&i )
  67.                break;
  68.  
  69.            if(j==31)
  70.              vst.push_back(i);
  71.       }
  72.  
  73.  
  74. // finding the paths 
  75.    for( size_t i =0 ; i < vst.size() ; i ++ )
  76.      for( size_t j = 0 ; j <  vst.size() ; j ++ )
  77.          for( size_t  k = 0 ; k < 32 ; k ++  )
  78.               {
  79.                 if( 1<<k & vst[i]  &&  1<<k & vst[j])
  80.                        break;
  81.  
  82.                   if(k==31)g[vst[i]].push_back(vst[j]);
  83.                }
  84.  
  85.  
  86. // finding the number of 1s in  a valid state 
  87.  
  88.        for( size_t i = 0 ; i < vst.size() ; i++ )
  89.             { int tp = 0 ;
  90.                for( int j = 0 ; j < 32 ; j++ )
  91.                    if(1<<j & vst[i])
  92.                        tp++;
  93.  
  94.                ct[vst[i]] = tp ;
  95.             }
  96.  
  97.  
  98.        ll sum = 0 ;
  99.  
  100.       memset(dp,-1,sizeof(dp));
  101.        for( size_t i = 0 ; i < vst.size() ; i ++ )
  102.            sum+= rec(vst[i],g, ct[vst[i]] ,1,ct);
  103.  
  104.       cout<< sum<<endl;
  105. }
  106.  
Success #stdin #stdout 0.4s 336704KB
comments (?)
stdin
copy 
2 4 4
stdout
copy 
2
https://ideone.com/QKspPN
language:
C++14 (gcc 8.3)
created:
8 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!