Comments
0

The following Python code works for calculating Catalan using online FFT.

from numpy import *

def catalan(n: int):
    f = [0] * (n + 1)
    f[0] = 1

    # calculate the contribution of f[l1:r1+1]*f[l2:r2+1] => f[l:r+1]
    def contrib(l1, r1, l2, r2, l, r):
        if l1 + l2 + 1 > r or r1 + r2 + 1 < l or l1 > r1 or l2 > r2 or l > r:
            return
        u = f[l1 : r1 + 1]
        v = f[l2 : r2 + 1]
        res = convolve(u, v)
        for i in range(l, r + 1):
            if i - 1 - l1 - l2 in range(0, len(res)):
                f[i] += res[i - 1 - l1 - l2]

    # CDQ on [l, r]
    def work(l, r):
        if l == r:
            return
        mid: int = (l + r) // 2
        work(l, mid)
        t = min([r - l, l - 1])
        contrib(0, t, l, mid, mid + 1, r)
        contrib(l, mid, 0, t, mid + 1, r)  # same as contrib(0, t, l, mid, mid + 1, r)
        contrib(l, mid, l, mid, mid + 1, r)

        work(mid + 1, r)

    work(0, n)
    return list(map(int, f))

print(catalan(20))
0

The link is here: CDQ convolution (online FFT) generalization with Newton method
0

A problem on this topic: 1765J - Hero to Zero. Considering its dual problem gives a clear sight on this problem.
+6

Here is another way to calculate $$$\binom{n}{m} \bmod 2$$$. We know that $$$\binom{n}{m} = \frac{n!}{m!(n - m)!}$$$. Define $$$P(n) = \max\{k : 2^k | n!\} = \sum_{i = 1}^{+\infty} \lfloor \frac{n}{2^i} \rfloor$$$. Then $$$\binom{n}{m} \bmod 2 = 1$$$ iff $$$P(n) - P(m) - P(n - m) = 0$$$.

Obviously, we can calculate $$$P(n)$$$ in $$$O(\log n)$$$ time, but here is a more efficient way. Suppose $$$n = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_m}$$$. Then

$$$ \begin{aligned} \sum_{i = 1}^{+\infty} \lfloor \frac{n}{2^i} \rfloor &= \sum_{j = 1}^m\sum_{i = 1}^{+\infty} \lfloor \frac{2^{a_j}}{2^i} \rfloor \\\\ &= \sum_{j = 1}^m\sum_{i = 1}^{a_j} 2^{a_j - i}\\\\ &= \sum_{j = 1}^m (2^{a_j} - 1)\\\\ &= n - m \end{aligned} $$$

Obviously, $$$m = \text{popcount}(n)$$$, the number of $$$1$$$(s) in binary form of $$$n$$$, which can be calculated fast in C++ with __builtin_popcount(n) or __builtin_popcountll(n) (when n is long long type). This improvement helped me from TLE to AC, and shows that __builtin_popcount really has very small constant. :P
+3

I met the same situation: cf-tool warns Cannot find csrf, and I can neither login nor parse problem statements.
+13

For problem E, consider for a certain $$$(i, j), i \le j$$$, how many times does $$$A_i ^ {A_{i + 1} \cdots A_j}$$$ contribute to the final answer, when putting XOR both between $$$A_{i - 1}$$$ and $$$A_i$$$, and between $$$A_j$$$ and $$$A_{j + 1}$$$.
+13

Also check this.
0

You can use the main site for viewing problem statement, while using the mirror sites for submission :P
0

Try submitting using Codeforces Tool, or through these mirror sites:
+1

If you sort the rows by the first element in increasing order, it turns out that blue rows is a prefix of the matrix.
0

Me too, but only 810 ms. record
+6

Iterate over a vector using auto:

std::vector<int> a = {1, 2, 3};
for (auto item : a)
    printf("%d\n", a);

or

for (auto it = a.begin(); it != a.end(); ++it)
    printf("%d\n", *it);
0

So is this one. Does the number 199199199199199 have a special meaning?