Random Task

Soru Metni:
Öyle bir n sayısı bulunuz ki n+1,n+2,n+3,...,2*n-1,2*n dizisindeki elemanlardan
kesinlikle m tanesi ikili gösterimlerinde tam olarak k tane bir biti içersin.

Girdi Formatı:
İlk ve tek satırda 2 adet sayı: m ve k(0 ≤ m ≤ 10^18; 1 ≤ k ≤ 64).

Çıktı Formatı:
Tek satırda istenen sayı n. n sayısının 1 ile 10^18 arasında olduğu garanti ediliyor.

Örnek Girdi:
1 1
Örnek Çıktı:
1

Örnek Girdi:
3 2
Örnek Çıktı:
5

Soru: codeforces.com/contest/431/problem/D

Çözüm Metni:

count(x) x sayısı içindeki bir bitleri sayısı k ise 1 değil ise 0 döndürsün.

f(n): n+1,n+2,n+3,...,2*n-1,2*n dizisinde tam olarak k tane bir biti içeren elemanların sayısı olsun.
f(n-1): n,n+1,n+2,...,2*n-3,2*n-2 dizisinde tam olarak k tane bir biti içeren elemanların sayısı olur.

f(n) = f(n-1) + count( 2*n-1 ) + count( 2*n ) - count( n ) olur.

count( 2*n ), count( n )'e eşit olur. 2*n sayısı n sayısının sonuna 1 adet 0 eklenmiş halidir.
O zaman bu iki sayıdaki bir bitleri sayısı eşittir.

f( n ) = f(n-1) + count( 2*n-1 ) olur.

Görüldüğü üzere n sayısı 1 artınca f fonksiyonunun değeri ya aynı kalır yada 1 artar.
Yani f azalmayan bir fonksiyondur.

f fonksiyonu azalmayan olduğu için cevabı binary search ile arayabiliriz.
Geriye kalan tek şey f(n) fonksiyonunu hesaplayabilmek.

1'den n'e kadar sayılardan kaç tanesi tam olarak k adet 1 biti içerdiğini bulursak iş biter.
Bunu da dinamik ile bulabiliriz.

dp[ind][k][t]
dp[70][70][2]

ind -> bulunduğum basamağın numarası kaç?
k -> kaç tane daha 1 biti koyacağım?
t -> şu anda bu basamağa ne koyarsam koyayım n sayısından küçük olur muyum?

Maliyet O( 70*70*2*log(10^18) ).

Çözüm Kodu:

#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cassert>
#include <queue>
#include <cstdlib>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <ctime>

#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define lli long long int
#define all( gg )        gg.begin(),gg.end()
#define foreach( gg,itit )        for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
#define FP( ii,aa,bb ) for( int ii=aa;ii<=bb;ii++ )
#define FM( ii,aa,bb ) for( int ii=aa;ii>=bb;ii-- )

using namespace std;

lli m,k,len,arr[70],dp[70][70][2];

lli bul( int ind,int k,int t ){
        if( ind==len+1 )        return k==0;
        lli &ret = dp[ind][k][t];
        if( ret!=-1 )        return ret;
        ret = bul( ind+1,k,!t ? 0 : arr[ind]==1 ? 0 : 1 );
        if( k and (!t or arr[ind]==1)  )        ret += bul( ind+1,k-1,t );
        return ret;
}

lli        F( lli orta ){
        len = 0;
        lli x = orta;
        while( x ){
                arr[++len] = (x&1);
                x >>= 1;
        }
        reverse( arr+1,arr+len+1 );
        memset( dp,-1,sizeof dp );
        return bul( 1,k,1 );
}

int main(){
        cin >> m >> k;
        lli bas=0,son=1e18,orta;
        while( bas<son ){
                orta = (bas+son)/2+1;
                if( F( 2*orta )-F( orta )>m )        son = orta-1;
                else        bas = orta;
        }
        cout << bas << endl;
}