HackerRank Combinatorics – Binomial Coefficients Revenge

Challenge: Binomial Coefficients Revenge

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464764349

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/bincoefrevenge/problem

Cerinta

The binomial coefficient _C(N, K)_ is defined as
_N! / K! / (N − K)!_ for _0 ≤ K ≤ N_.  
Here _N! = 1 \* 2 \* ... \* N_ for _N ≥ 1_, and _0! = 1_.

You are given a prime number _P_ and a positive integer _N_. 

_A<sub>L</sub>_ is defined as the number of elements in the sequence _C(N, K)_, such that, _P<sup>L</sup>_ divides _C(N, K)_,
but _P<sup>L+1</sup>_ does not divide _C(N, K)_. Here, _0 ≤ K ≤ N_.


Let _M_ be an integer, such that, _A<sub>M</sub> > 0_,
but _A<sub>L</sub> = 0_ for all _L > M_.
Your task is to find numbers _A<sub>0</sub>, A<sub>1</sub>, ..., A<sub>M</sub>_.

**Input Format**  
The first line of the input contains an integer _T_, denoting the number of test cases.
The description of _T_ test cases follows.
The only line of each test case contains two space-separated integers _N_ and _P_.

**Output Format**  
For each test case, display _M + 1_ space separated integers
_A<sub>0</sub>, A<sub>1</sub>, ..., A<sub>M</sub>_
on the separate line.

**Constraints**

1 ≤ T ≤ 100  
1 ≤ N ≤ 10<sup>18</sup>  
2 ≤ P < 10<sup>18</sup>  
P is prime  


**Sample Input**

    3
    4 5
    6 3
    10 2

**Sample Output**

    5
    3 4
    4 4 1 2


**Explanation**  

**Example case 1.** Values _C(4, K)_ are _{1, 4, 6, 4, 1}_.
Each of them is not divisible by 5.
Therefore, _A<sub>0</sub> = 5_, _A<sub>1</sub> = 0_, _A<sub>2</sub> = 0_, ..., hence the answer.


**Example case 2.** Values _C(6, K)_ are _{1, 6, 15, 20, 15, 6, 1}_.
Among them _1, 20, 1_ are not divisible by _3_,
while remaining values _6, 15, 15, 6_ are divisible by _3_, but not divisible by _9_.
Therefore, _A<sub>0</sub> = 3_, _A<sub>1</sub> = 4_,
_A<sub>2</sub> = 0_, _A<sub>3</sub> = 0_, ..., hence the answer.


**Example case 3.** Values _C(10, K)_ are _{1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1}_.
Among them _1, 45, 45, 1_ are not divisible by _2_,
values _10, 210, 210, 10_ are divisible by _2_, but not divisible by _4_,
value _252_ is divisible by _4_, but not divisible by _8_,
finally, values _120, 120_ are divisible by _8_, but not divisible by _16_.
Therefore, _A<sub>0</sub> = 4_, _A<sub>1</sub> = 4_,
_A<sub>2</sub> = 1_, _A<sub>3</sub> = 2_,
_A<sub>4</sub> = 0_, _A<sub>5</sub> = 0_, ..., hence the answer.

Cod sursa

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        unsigned long long N, P;
        cin >> N >> P;

        vector<unsigned long long> dig;
        if (N == 0) {
            dig.push_back(0);
        } else {
            while (N > 0) {
                dig.push_back(N % P);
                N /= P;
            }
        }

        int d = (int)dig.size();
        vector<unsigned long long> dp0(d + 1, 0), dp1(d + 1, 0);
        dp0[0] = 1; // no digits processed, borrow=0

        for (int i = 0; i < d; ++i) {
            vector<unsigned long long> ndp0(d + 1, 0), ndp1(d + 1, 0);
            unsigned long long ni = dig[i];

            for (int c = 0; c <= i; ++c) {
                // from borrow = 0
                if (dp0[c]) {
                    unsigned long long ways_nb0 = ni + 1;   // k_i <= ni
                    unsigned long long ways_nb1 = P - ways_nb0;

                    ndp0[c] += (unsigned long long)((__int128)dp0[c] * ways_nb0);
                    if (ways_nb1) ndp1[c + 1] += (unsigned long long)((__int128)dp0[c] * ways_nb1);
                }

                // from borrow = 1
                if (dp1[c]) {
                    unsigned long long ways_nb0 = ni;       // k_i <= ni-1
                    unsigned long long ways_nb1 = P - ways_nb0;

                    if (ways_nb0) ndp0[c] += (unsigned long long)((__int128)dp1[c] * ways_nb0);
                    ndp1[c + 1] += (unsigned long long)((__int128)dp1[c] * ways_nb1);
                }
            }

            dp0.swap(ndp0);
            dp1.swap(ndp1);
        }

        vector<unsigned long long> A(d + 1, 0);
        for (int c = 0; c <= d; ++c) A[c] = dp0[c]; // final borrow must be 0

        int M = d;
        while (M > 0 && A[M] == 0) --M;

        for (int i = 0; i <= M; ++i) {
            if (i) cout << ' ';
            cout << A[i];
        }
        cout << '\n';
    }

    return 0;
}