When I was making a problem, I needed to calculate $$$C_r^n$$$ modulo a non-prime big number. So, I found a simpler method I haven't seen shared, and I'm excited to explain it.

Prerequisites:

• Modular arithmetic

• Factorization

• Binary exponentiation

• Knowing $$$\binom{n}{r}$$$ and Euler's totient function

The problem is the modular inverse. We can get it for a number $$$x$$$ if and only if $$$x$$$ is coprime with the modulus. But in a lot of problems, we just need to undo a previous operation,

$$$C_3^5 = \frac{5!}{3! \cdot 2!}$$$. We delete one $$$3$$$ and two $$$2$$$s from $$$5!$$$.

So why have we never thought to store it in a frequency array?

My idea is that when multiplying, we use the modular arithmetic formulas, and when dividing, we will count the frequency of each prime number in the modulus and delete it from $$$n!$$$, So we need to first calculate $$$n!$$$ without the primes in the modulus and count the frequency for each prime. Then, when you need to know the answer, you can iterate over the frequency array :)

But what if I divided $$$\frac{1}{2}$$$? It will not even happen, so what is the meaning of $$$\frac{1}{2}$$$?

I think it looks like imaginary numbers. $$$\sqrt{−1}^2 = −1$$$. It's easy to understand :)

We will find the prime factors of a number with any method (normal factorization is good enough). The modular inverse for a coprime number is $$$x^{phi(mod) - 1}$$$ (it's not working in power towers, but here I think it's enough here), $$$phi(x)$$$ is a multiplicative function you can easily calculate in $$$O(\sqrt{n})$$$.

So we can imagine a number, let's call him imaginary-modular-integer (imint), and make the necessary operations only (I mean * and /, no need for *= and /=).

Note: if you need to divide after adding, my trick will never work unless you make it better :) (tell me if you did).

You can see the code here:

struct imint {
    std::vector<__uint128_t> _primes, _power;
    __uint128_t _modulo, _phi;
    __uint128_t _value;

    void build(__uint128_t _target) {
        _modulo = _target, _phi = _modulo, _value = 1;
        for (__uint128_t i = 2; i * i <= _modulo; ++i)
            if (_modulo % i == 0) {
                while (_modulo % i == 0) _modulo /= i;
                _phi -= _phi / i;
            }
        if (_modulo > 1) _phi -= _phi / _modulo;
        _modulo = _target;
        for (__uint128_t i = 2; i * i <= _target; ++i)
            if (_target % i == 0) {
                _primes.push_back(i);
                while (_target % i == 0) _target /= i;
            }
        if (_target > 1) _primes.push_back(_target);
        _power.assign(_primes.size(), 0);
    }

    friend imint operator*(__uint128_t a, imint b) {
        for (size_t i = 0; i < b._power.size(); i++)
            while (a % b._primes[i] == 0) {
                b._power[i]++;
                a /= b._primes[i];
            }
        (b._value *= a) %= b._modulo;
        return b;
    }

    friend imint operator/(imint a, imint b) {
        assert(a._modulo == b._modulo);
        for (size_t i = 0; i < a._power.size(); ++i)
            a._power[i] -= b._power[i];
        __uint128_t _exponentiation = a._phi - 1;
        while (_exponentiation) {
            if (_exponentiation & 1)
                (a._value *= b._value) %= a._modulo;
            (b._value *= b._value) %= a._modulo;
            _exponentiation >>= 1;
        }
        return a;
    }

    __uint128_t real() {
        __uint128_t _real = _value;
        for (size_t i = 0; i < _power.size(); ++i) {
            __uint128_t _exponentiation = _power[i];
            __uint128_t _base = _primes[i];
            while (_exponentiation) {
                if (_exponentiation & 1)
                    (_real *= _base) %= _modulo;
                (_base *= _base) %= _modulo;
                _exponentiation >>= 1;
            }
        }
        return _real;
    }
};

After using this code as a template (please understand it first, don't just copy it!), you can write this:

dp[0].build(m);
for (int i = 1; i <= n; i++) dp[i] = i * dp[i - 1];

It will add $$$\lg(\lg(n))$$$ to the time complexity :(

When you need to calculate the answer, you can use $$$real()$$$ function.

Important Note: Do not write

dp[n] / (dp[r] * dp[n - r]);

. Instead, you should use:

(dp[n] / dp[r] / dp[n - r]).real();

It's not hard and pretty cool. If you know stars and bars and sieve, you can try to solve the easy version of my problem: Invitation

These are the hardest two problems from Today's contest in Asyut Hack Club :)

Edit:

standard problem with this trick ABC 425E

There was a bug in my code (It's fixed now), Thanks Baraa-Ahmed for fixing the bug

I liked this problem a lot :)

I searched after contest for a fast solution and I found an O(n^(2/3)) solution for it :)

This problem Is a famous problem and has a lot of github codes, He want the partial sum for prime omega function

But I liked this problem, because there is no pupil will know that problem is duplicated and this is a problem for a pupil :)

I searched after the contest but in the contest I didn't know that :o

If you like challenge you can try to solve it with O(n^(2/3)) solution here

I just solved the V-Subtree problem on AtCoder DP Contest, and after solving it, I couldn't find anyone who solved it iteratively, so I decided to share my code with you :)

My code (without my template)

My idea was that, to do a topological sort iteratively, I thought I had to use Kahn's algorithm. When I found that I was getting a wrong answer, I tried to find the problem, and it turned out that the tree was undirected. After some deep thinking, I realized that I could treat the tree as directed, so I sorted the elements by their distance from the root (any root can be taken since it's undirected). Then, I went on to write the answer code :)

Hello Codeforces!!

A few days ago, I wrote a code for BigInt and BigFloat classes and i would like to share it with you for feedback and improvement. For the code Press here.

Note: My BigFloat class stores numbers as a numerator and denominator to efficiently represent fractions like (1/3) without wasting data.

You can use functions like floor(object, n), ceil(object, n), or round(object, n) to extract the first n decimal places or convert the object to a string with a specified precision using str(n).

I've also implemented all comparison operations for BigFloat objects.

Note: The modulus operation for BigFloat currently calculates the modular inverse of the number. While this is interesting, you might also consider offering standard modulus behavior for users.

The Important Operations is

Multiplication: O((n + m) * log(n + m)) using FFT (Fast Fourier Transform). However, for small values of m, O(n * m) might be faster due to lower constant factors. (Here, n refers to the number of digits in the first number, and m refers to the number of digits in the second number.)

Addition and Subtraction: O(max(n, m)) for efficient handling.

Division and Modulus: O(n * m).

Bitwise Operations: O(n * log(n)).

GCD (Greatest Common Divisor) and LCM (Least Common Multiple): O(n * n * log(n)).

Other Mathematical Functions: I've added ceil, floor, round, abs, sqrt, and cbrt (using Newton's Method) to enhance the functionality of the BigFloat class.

Finally, I would like to thank mostafa133 for his help for this code and TryOmar for training me during the beaver scholarship.