Adjacent_Bit_Sum_Count.cpp

/*
    Problem Link : https://www.spoj.com/problems/GNYR09F/
    Problem Name : Adjacent Bit Count
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef set<int> si;
typedef set<int,greater<int>> sgi;
typedef stack<int> sti;
typedef stack<ll> stl;
typedef unordered_set<int> usi;
typedef unordered_set<ll> usl;
typedef queue<int> qi;
typedef queue<ll> ql;
typedef unordered_map<int,int> umi;
typedef unordered_map<ll,ll> uml;
typedef unordered_map<int,ll> umil;
typedef unordered_map<ll,int> umli;
typedef map<int,int> mi;
typedef map<ll,ll> ml;
typedef map<int,ll> mil;
typedef map<ll,int> mli;
#define endl "\n"
#define pb push_back
#define f(i,k,n) for(int i=k;i<n;i++)
#define ef(i,k,n) for(int i=k;i<=n;i++)
#define fl(i,k,n) for(ll i=k;i<n;i++)
#define efl(i,k,n) for(ll i=k;i<=n;i++)
#define vsort(v) sort(v.begin(),v.end())
#define intscan(a) scanf("%d",&a)
#define llscan(a) scanf("%lld",&a)
#define println(a) printf("%d\n",a)
#define llprintln(a) printf("%lld\n",a)
#define prints(a) printf("%d ",a)
#define llprints(a) printf("%lld ",a)
#define coutln(a) cout<<a<<endl
#define couts(a) cout<<a<<" "
#define cout(a) cout<<a
ll dp[105][105][2];
ll func(int n,int k,bool flag){
    if(k<0)
        return 0;
    if(n==0)
        return (k || flag)?0:1;
    if(dp[n][k][flag]!=-1)
        return dp[n][k][flag];
    return dp[n][k][flag] = flag ? func(n-1,k,0)+func(n-1,k-1,1):func(n-1,k,0)+func(n-1,k,1);
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
    int t;
    cin>>t;
    f(i,0,t){
        memset(dp,-1,sizeof(dp));
        int a,b,c;
        cin>>a>>b>>c;
        prints(a);
        llprintln(func(b,c,0)+func(b,c,1));
    }
    return 0;
}