I have done a matrix multiplication program that runs ~50x faster than plain naive implementation and ~3x faster than IKJ-order with modular tricks in just 55 lines of code (see lines 256 to 310 in my submission).

Typically, to get this kind of speed (top 4 on Library Checker), you would have to spend 300+ lines of code for a Strassen implementation.

Here is the link: https://judge.yosupo.jp/submission/310249. A lot of the code was based on https://mirror.codeforces.com/blog/entry/101655, aside from the tmp part.

I have a problem that reduces to doing 2 kinds of queries:

• Add a number in $$${1,-1}$$$ to a range.
• Query the number of 0s in a suffix. It's guranteed that the array is nonnegative.

Constraints: $$$n\leq 10^5, Q\leq 192\cdot10^5$$$. My best solution did this problem in about 3.5 seconds using sqrt decomposition.

Here is my best implementation for 472G: 331895855. It works the same way as 8014415, just with AVX2 intrinsics instead of SSE code. It's about 30% faster than popcnt (which is already fast) and 2-3x faster than the old SSE code. It's currently the fastest on CF.

I just did a problem that asks you for $$$q$$$ queries of $$$[x^k](\prod_{i=1}^{n}(1+x^i))^2\ mod \ 10^9 + 7$$$. $$$n$$$ is given beforehand and $$$k$$$ is given in the queries. Constraints: $$$n,k,q \leq 10^5$$$. Is there a simple solution that doesn't involve a huge polynomials template that runs in $$$o(NK)$$$? (The time limit is 3 seconds).

https://docs.google.com/document/d/1HExf0T4Y3G9gEdyVN9MBoq8LT-9fitFvqIRf7w_sTC8/edit?usp=sharing

https://pt13762104.github.io/Codeforces_1771F_optimization.pdf

I want to ask this problem: There are $$$Q$$$ queries and 2 strings $$$S,T$$$ of length $$$N$$$, each containing $$$l_1,l_2,r_1,r_2$$$, which asks for wildcard matching on the substrings $$$S[l_1...r_1]$$$ and $$$T[l_2...r_2]$$$ (Assume $$$r_1-l_1=r_2-l_2$$$). Can it be done faster than $$$O(NQ)$$$?

I've been using this fast I/O library for a few times now. 323598048. But when I submit it to 782F - Axel and Marston in Bitland, with C++23 the code will just fall off at test 9. Even worse is that changing the parameters didn't help. C++20 works fine and I have tested it on my PC. Also it didn't work for 914F - Substrings in a String too: 323598468. I suspect this are related to death vectors, but I don't use cin, so it might not be related. Can anyone give me an insight? Maybe the I/O template I'm using has bugs?

In the problem 914F - Substrings in a String, the suffix array construction constant is rather big. The update queries can reach nearly 2 seconds in runtime for $$$O(n\sqrt{n})$$$ operations. The $$$O(n)$$$ suffix array algorithm I used is only a bit faster than $$$O(n\log{n})$$$ one used normally. Is there actually a fast suffix array algorithm that works for small arrays like these?

Is there an algorithm that solves this problem for any $$$k$$$? https://mirror.codeforces.com/problemset/gymProblem/101806/X.

Any complexity is allowed, if it solves the problem for $$$k\leq5$$$ with the original constraints.