(UVa) 1228 - Integer Transmission

https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=847&problem=3669

DP (?)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

typedef vector<int> vint;
typedef unsigned long long ULL;
const int MAX_N = 68;

#define SZ(x) ((int)(x).size())

vint vv[MAX_N];

ULL solve_mx(int n,vint v,ULL k,int d) {
    for (int i=0;MAX_N>i;i++) vv[i].clear();
    vint ret;
    for (int i=0;SZ(v)>i;i++) {
        //cout<<"i = "<<i<<" , v = "<<v[i]<<endl;
        if (v[i] == 1) ret.push_back(1);
        else {
            vv[min(n-1,d+i)].push_back(0);
        }
        for (int j:vv[i]) {
            ret.push_back(j);
        }
    }
    reverse(ret.begin(),ret.end());
    ULL ret1=0;
    ULL now=1;
    for (int i=0;SZ(ret)>i;i++) {
        ret1 += ret[i]*now;
        now*=2;
    }
    return ret1;
}

ULL solve_mn(int n,vint v,ULL k,int d) {
    for (int i=0;MAX_N>i;i++) vv[i].clear();
    vint ret;
    for (int i=0;SZ(v)>i;i++) {
        if (v[i] == 0) ret.push_back(0);
        else {
            vv[min(n-1,d+i)].push_back(1);
        }
        for (int j:vv[i]) {
            ret.push_back(j);
        }
    }
    reverse(ret.begin(),ret.end());
    ULL ret1=0;
    ULL now=1;
    for (int i=0;SZ(ret)>i;i++) {
        ret1 += ret[i]*now;
        now*=2;
    }
    return ret1;
}

ULL dp[MAX_N][MAX_N];

int pos0[MAX_N],pos1[MAX_N];

int main () {
    int kase=0;
    int n;
    while (scanf("%d",&n) != EOF) {
        if (!n) break;
        int d;
        ULL k;
        scanf("%d %llu",&d,&k);
        vint v;
        v.resize(n);
        ULL kk=k;
        int tmp=0;
        while (kk>0) {
            v[tmp++]=(kk&1);
            //cout<<"tmp = "<<tmp<<" , val = "<<(kk&1)<<endl;
            kk>>=1;
        }
        reverse(v.begin(),v.end());
        ULL mn=solve_mn(n,v,k,d);
        ULL mx=solve_mx(n,v,k,d);
        memset(dp,0,sizeof(dp));
        memset(pos1,0,sizeof(pos1));
        memset(pos0,0,sizeof(pos0));
        int cnt0=0,cnt1=0;
        //pos0[0] = pos1[0] = -123456789;
        for (int i=0;n>i;i++) {
            if (v[i] == 1) pos1[++cnt1] = i;
            if (v[i] == 0) pos0[++cnt0] = i;
        }
        /*
         for(int i = 0;i <= cnt[0];i++)
         for(int j = 0;j <= cnt[1];j++)
          {
              if(i != cnt[0] && f_num[i+1][0] + d >= f_num[j][1]) f[i+1][j] += f[i][j];
              if(j != cnt[1] && f_num[j+1][1] + d >= f_num[i][0]) f[i][j+1] += f[i][j];
          }
        */
        dp[0][0] = 1;
        for (int i=0;cnt0>=i;i++) {
            for (int j=0;cnt1>=j;j++) {
                if (pos1[j] <= d + pos0[i+1] && i+1 <= cnt0) {
                    dp[i+1][j] += dp[i][j];
                }
                if (pos0[i] <= d + pos1[j+1] && j+1 <= cnt1) {
                    dp[i][j+1] += dp[i][j];
                }
            }
        }
        ULL count = dp[cnt0][cnt1];
        printf("Case %d: %llu %llu %llu\n",++kase,count,mn,mx);
    }
}