Hey, welcome back!
1. How does your code handle cases where the ratio of n to k is very high, say when n = 300, k = 2? |
It fails.
Remember what the math is here: N represents the number of bits available, and the result represents how many values we can get out of N bits (with restrictions). The largest value we can get is if K=1, requiring N+1 bits to represent as an integer value.
For example, if N=8 and K=1, there are 256 possible values, which is 1'0000'0000 in binary — a value requiring nine bits to represent.
So... any
n greater than 63 (number of unsigned bits in a
signed long int
on modern systems) will fail if K is small enough. 300 is
waaaay too many bits to represent in a machine integer type.
The answer is required to be provided MOD 10e9+7 since the results could be so large |
Yes. ATM I haven’t done more than gloss my eyes over your code (sorry), but
where you apply the remainder function may make a difference. I might come back and give it another look later to see if that is the case.
The correct answer for N=300,K=2 (mod 1000000007) is
893039802
. Is that not what you are getting?
2. I actually tried running your code with the above values (n = 300, k = 2) |
You have discovered UB — Undefined Behavior (
https://en.cppreference.com/w/cpp/language/ub).
Since N is too big, the math fails for the integer type, and you wind up with unexpected behavior.
I suspect that the loop on line 70 is the culprit:
69 70 71
|
// For each m multiples of K
for (long m = 1; m*K <= N; m++)
{
|
Since
m*K
overflows it can never be larger than
N
, hence infinite loop.
3. [Usage magic] Pls, what is going on here?! |
The
string_to<long>()
function throws an exception if the argument string cannot be converted to a
long
. 😉
If you actually wanted to calculate astronomical values you’d need a bignum
A
bignum is an arbitrary-precision integer value, meaning it can have as many digits as memory allows. The Boost Libraries (
https://www.boost.org/) conveniently provide us access to easy bignums.
If you are serious about using Python, you should have Boost Libraries installed. For the following it is enough to simply have the Boost header files properly installed — the cpp_int bignum is a header-only library.
If you are on Windows, use the MSVC installer again and make sure to add the Boost Libraries as part of your install package.
If you are on a Debian-based Linux you can simply sudo apt-get install libboost-all-dev
.
Alas, cpp.sh cannot link with Boost, so you’ll have to use https://godbolt.org/ or something that can.
Here is my program with the minor adjustment of using a bignum instead of a machine long int:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
|
#include <ciso646>
#include <filesystem>
#include <iostream>
#include <sstream>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>
using integer = boost::multiprecision::cpp_int;
int usage( std::filesystem::path exename, int exit_code = 1 )
{
#define T(s) s "\n"
std::cout <<
T("usage:")
T(" " << exename.filename().string() << " N K")
T("")
T("Compute the number of binary strings possible when:")
T(" • each string has length N digits in [0,1]")
T(" • every 0 in the string must be in a block of")
T(" some multiple of K consecutive 0s.");
#undef T
return exit_code;
}
template <typename T>
T string_to( const std::string& s )
{
T value;
std::istringstream ss( s );
ss >> value >> std::ws;
if (!ss.eof()) throw std::invalid_argument("T string_to()");
return value;
}
integer choose( integer n, integer k )
{
// Compute the Binomial Coefficient
// (n choose k) = n! / k!(n-k)!
if (n < k) return 0;
if (n == k) return 1;
integer product = 1;
// product ←– n! / (n-k)!
integer n_minus_k = n-k;
while (n > n_minus_k)
{
product *= n--;
}
// product ←– product / k!
while (k > 1)
{
product /= k--;
}
return product;
}
integer solve( integer N, integer K )
{
if (N <= 0 or K < 0) return 0;
if (K == 0) return 1;
// There are always possible strings of length N '1's.
integer sum = 1;
// For each m multiples of K
for (integer m = 1; m*K <= N; m++)
{
// add in the number of possible arrangements
sum += choose( N - m*K + m, m );
}
return sum;
}
int main( int, char ** argv )
try
{
integer N = string_to <integer> ( argv[1] );
integer K = string_to <integer> ( argv[2] );
std::cout << solve( N, K ) << "\n";
return 0;
}
catch (...)
{
return usage( argv[0] );
}
|
Again, make sure boost is properly in your include path. Compile as before.
Now we can get the answer to your question:
$ ./bs 300 2
359579325206583560961765665172189099052367214309267232255589801
$ █ |
That is a
lot of combinations!
$ tclsh
% expr {359579325206583560961765665172189099052367214309267232255589801 % 1000000007}
893039802
% exit |
An even bigger number is:
$ ./bs 300 1
2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376
$ █ |
We can plug 2
300 into any bignum calculator and verify that it is correct.
$ tclsh
% expr {2**300}
2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376
% exit
$ █ |
Always feel free to ask questions.
I will probably peruse your code in a day or two.