izlyforever's blog

cpplibforCP
By izlyforever, history, 3 years ago, In English

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 < n, p < 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.

  • Vote: I like it
  • +57
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Doesn't atcoder have a similar library? No offense, I highly appreciate your efforts but just wanted to know the reason of creating this.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I learnt a lot from AtCoder library.

    I given a reference in cpplibforCP, however many primary math algorithms don't supported in AtCoder.

    cpplibforCP contains many math algorithm, and almost all algorithm related to polynomials.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok, nice. Great Work!!!

      → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The code quality looks great! Thank you for the effort.

On the other hand, if you want people to genuinely use this library, then you need to enhance the documentation. Currently it is quite poor. Importantly, you need to document the assumptions your functions make. Otherwise, only you can use it during the contest, assuming you didn't forget for example:

  • whether something is 0-indexed or 1-indexed.
  • complexity of the codes
  • some other algorithm specific stuff like one of variables actually needs to be prime

AtCoder's template library does this job perfectly, their documentation is mastery. KACTL documentation is very solid, too. Try to look around and improve! (unless you want to have a toy project just for yourself of course...)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for you advice, I will try my best to enhance the documentation.

    → Reply