Hello, codeforces

I write a personal C++ template for Competitive Programming Algorithms. It contains many common algorithms, especially mathematical ones.

I know that the more you use it, the more reliable it is. Almost all template are tested in a Chinese OJ: LuoGu. However, no one can ensure that no bugs in their codes.

Thanks in advance if you find some bugs or give other testes.

As we know, programmers hate two things:

• writing documents
• others who don't writing documents

Here is Document and Source Code for detail.

As an example, you can solve $$$n! \mod p$$$ in SPOJ where $$$0 \lt n, p \lt 10^{11}$$$, use following simple code.

#include <bits/stdc++.h>
#define clog(x) std::clog << (#x) << " is " << (x) << '\n';
using LL = long long;
#include "../cpplib/math.hpp"

// https://www.spoj.com/problems/FACTMODP/en/
int main() {
	// freopen("in", "r", stdin);
	std::cin.tie(nullptr)->sync_with_stdio(false);
	int cas = 1;
	std::cin >> cas;
	while (cas--) {
		LL n, p;
		std::cin >> n >> p;
		std::cout << factorial(n, p) << '\n';
	}
	return 0;
}

my submission contains 925 lines after copy some codes from math.hpp

UDP: The document for math.hpp have been enhanced with the help of kpw29's advice.

UDP2: non-const member variables terminate with _, and std::move, std::forward are used.

Successful hacks makes Codeforces better. Here are at least two reasons:

• A successful hack helped stable ProblemSet
• The defenders can quickly find bugs in their own code through the test provided by hackers

So hackers make contributions to the community, they deserve some contribution.

UDP1：

VLamarca's number of hacks(number of problem hacks) also a good suggestion.

If it does increases contribution, $$$\frac{100 x}{100 + x}$$$ contribution may be simple nice, where $$$x$$$ is number of problem hacks.

Fade hacks mentioned by Real_Father_Of_Ash is really annoying, it does know how to improve, but I believe that people who are loving codeforces and care about contribution won't do like this.

Really hope admin: MikeMirzayanov and geranazavr555 could take it into consideration.

nihal2001 posted a blog for asking the following question:

There are $$$n$$$ stones, two players take turn to choose $$$x$$$ stones, such that $$$1 \leq x \leq n$$$ and $$$x \And n = 0$$$. The one who cannot make choose lose.

Determine who is the winner, The first one or the second?

I proved that If $$$n$$$ belongs to https://oeis.org/A295897, the second player win(can be solved in $$$O(\log n)$$$).

My Question(Multiple piles version of above question):

There are $$$n_1, \cdots, n_m$$$ stones, two players take turn to choose an index $$$i$$$ and $$$x_i$$$ stones, such that $$$1 \leq i \leq m$$$, $$$1 \leq x_i \leq n_i$$$ and $$$x_i \And n_i = 0$$$. The one who cannot make choose lose.

Who will be the winner?

This turn out to compute Sprague-Grundy function for $$$n_1 \cdots, n_m$$$. The first player win if and only if $$$sg(n_1) \wedge \cdots \wedge sg(n_m) \neq 0$$$

I know how to compute $$$sg(n)$$$ in $$$O(n^2 \log n)$$$, but I can't give it a formula or compute efficiently like $$$O(\log n)$$$ or $$$O(\log^2 n)$$$

Thanks in advance.

UPD: $$$O(n^{log_2 3} \log n)$$$ implement based on wery0's comment.

UPD2: $$$O(n^{log_2 3})$$$ implement based on wery0's talk.