Numim număr k-binar un număr natural care în scrierea sa în baza 2 are exact k cifre de 1. De exemplu numărul 23 este 4-binar pentru că el se scrie în baza 2 sub forma 10111 și conține exact patru biți de 1.

Cerința

Pentru valorile date ale lui N și k, să se calculeze suma tuturor numerelor k-binare strict mai mici decât N. Deoarece sumele sunt foarte mari, acestea vor fi calculate modulo 1234567.

Date de intrare

Fișierul de intrare kbin.in conține pe prima linie valorile N şi k separate printr-un spațiu.

Date de ieșire

Fișierul de ieșire kbin.out va conţine pe prima linie un singur număr natural s reprezentând suma cerută modulo 1234567.

Restricții și precizări

2 ≤ N ≤ 10¹⁵
0 ≤ k ≤ 50
Pentru 30% din punctaj N ≤ 10⁶
Pentru 60% din punctaj N ≤ 10⁹ şi k ≤ 7

Exemplu

kbin.in

15 3

kbin.out

Explicație

1 – 1
2 – 10
3 – 11
4 – 100
5 – 101
6 – 110
7 – 111
8 – 1000
9 – 1001
10 – 1010
11 – 1011
12 – 1100
13 – 1101
14 – 1110
Numerele care au 3 biți de 1 sunt 7, 11, 13, 14.
s = 7 + 11 + 13 + 14 = 45.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema kbin:

#include <fstream>
#define V 1234567
#define M 100
using namespace std;
ifstream in("kbin.in");
ofstream out("kbin.out");
long long s,sp2f,c[M][M],p2[M],sp2[M],b[M];
int main()
{
    long long a,k;
    in>>a>>k;
    long long x=a,n=0;
    int sb=0;
    while(x>0){
        b[n]=x%2;
        sb+=b[n];
        x/=2;
        n++;
    }
    p2[0]=1;
    sp2[0]=1;
    c[0][0]=1;
    for(int i=1;i<=n;i++){
        p2[i]=p2[i-1]*2;
        p2[i]%=V;
        sp2[i]=sp2[i-1]+p2[i];
        sp2[i]%=V;
        c[i][0]=1;
        for(int j=1;j<=i;j++){
            c[i][j]=c[i-1][j-1]+c[i-1][j];
            c[i][j]%=V;
        }
    }
    if(p2[n-1]==a){
        s=c[n-2][k-1]*sp2[n-2];
    }
    else{
        int ik,i;
        for(i=n-1,ik=k;i>0 && ik>0;i--){
            if(b[i]==1){
                s+=sp2[i-1]*c[i-1][ik-1];
                s%=V;
                s+=sp2f*c[i][ik];
                s%=V;
                ik--;
                sp2f+=p2[i];
                s%=V;
            }
        }
        if(ik==0 && sp2f!=a)
            s+=sp2f;
    }
    s%=V;
    out<<s<<'\n';
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2557 kbin

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2557 kbin de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2557 kbin