There is no difference between Rating and Rating(all)

ios_base::sync_with_stdio(0);cin.tie(0); welcome you! So use only cin/cout if you are a C++ player

Is there any detail editorial for problem I using fwt

• the case $$$F(n,k) = 1$$$ is trivial.
• the case $$$F(n,k) = \binom{n}{k}$$$ can be translated into

• the other case, I don't know

multiply the polynomials with same degree using fast power (otherwise I got a TLE due to my slower nft template) and multiply the smallest polynomials in degree each time.

Read this Code may help, Sadly the website you provided does not support C++17.

How to solve problem B if you change $$$c_i = \gcd(b_i, b_{i + 1})$$$

Thanks for Reference of how to deal with interactive problem

Thanks!

oh my god, stupid dna049!!!

What wrong with my 91425950 for problem C in div2

Checker Log wrong answer Integer -1 violates the range [1, 4]

thus for the sample, why the following is wrong answer atoiz

1 4 
0 0 -8 -4
1
-1
2 4
-3 6 0

Thanks ~

Won't faster... sorry

slightly faster than origin %: 827ms vs 643ms in my computer

#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;
constexpr LL M  = 1e9 + 7;
constexpr int  k = std::__lg(M) + 2;
constexpr LL m = (1LL << k) / M;

const int N = 1e8 + 2;
LL fac[N];
void init1(){
	fac[0] = 1;
	for (int i = 1; i < N; ++i) fac[i] = fac[i - 1] * i % M;
}
void init2() {
	auto mod = [&](LL &a) {
		LL r = a - ((a * m) >> k) * M;
		if (r >= M) r -= M;
	};
	fac[0] = 1;
	for (int i = 1; i < N; ++i) mod(fac[i] = fac[i - 1] * i);
}
int main() {
	//freopen("in","r",stdin);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	auto start1 = std::chrono::high_resolution_clock::now();
	init1();
	auto end1 = std::chrono::high_resolution_clock::now();
	std::cout << "Time used: " << std::chrono::duration_cast<std::chrono::milliseconds>(end1 - start1).count() << " (ms)" << std::endl;

	auto start2 = std::chrono::high_resolution_clock::now();
	init2();
	auto end2 = std::chrono::high_resolution_clock::now();
	std::cout << "Time used: " << std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count() << " (ms)" << std::endl;

	return 0;
}

So smart your link is!

Auto comment: topic has been updated by jianglyFans (previous revision, new revision, compare).

Auto comment: topic has been updated by jianglyFans (previous revision, new revision, compare).

Auto comment: topic has been updated by jianglyFans (previous revision, new revision, compare).

How to solve Problem E?

I even don't understand the sample: [[5,1],[2],[7,4,3],[6]] ---> [[2],[7,5,4,3,1],[6]]

[[5,1],[2],[7,4,3],[6]] ---> [[5],[2],[7,4,3,1],[6]] ---> [[5,4,3,1],[2],[7],[6]] ---> [[],[2],[7,5,4,3,1],[6]] 3 steps is ok! why the answer is 5 ?

Amazing, provide a new idea to cost compile-time instead of exec-time ! It may useful for particluar questions since CP only care about exec-time.

But: ‘constexpr’ loop iteration count has limit of 262144 (use ‘-fconstexpr-loop-limit=’ to increase the limit), and we can't use -fconstexpr-loop-limit= parameter in CP, sadly this ideal may can't put prime sieve in practice even ...._.._ provide C++14(So C++17 works) version of your idea.

Amazing!

How to compute the exact value of $$$a_n$$$ by OGF ? for example the case: the OGF of Fibonacci numbers $$$\Rightarrow F(x) = \frac{x}{1-x-x^2}$$$

Or for unkown problem, we compute the OGF of $$$a_n$$$, and find a recurrence array with same OGF of $$$a_n$$$, then use matrix power(or poly mod power) to deal with recurrence array, finally we get $$$a_n$$$.

• $$$a_{3n} = a_{3n-1} + 2 a_{3n-2} + 4$$$
• $$$a_{3n+1} = a_{3n} + 2 a_{3n-1} = 3 a_{3n-1} + 2 a_{3n-2} +4$$$
• $$$a_{3n+2} = a_{3n+1} + 2 a_{3n} = 5 a_{3n-1} + 6 a_{3n-2} + 12$$$

and then write in matrix form

Thanks! I understand how you get the geometric sums, by calculating generating function. Really much nicer!

See my comment

See my comment

Four methods for Problem D:

Method 0. using dp as the Editorial given： $$$a_i = a_{i-1} + 2 \cdot a_{i-2} + (i \% 3 == 0?4:0)$$$ (use $$$a_i$$$ instead of $$$dp_i$$$ for short) Code: 84808226

there is a typing mistake in Brief Solution of D: $$$(i \% 3 == 0?4:0)$$$ instead of $$$(i \% 3 == 0?1:0)$$$ DeadlyCritic

Expand the above recurrence formula we have

with $$$a_0 = a_1 = a_2 = 0$$$, and $$$A$$$ indicate the coefficient matrix.

Methods below are $$$O(\log n)$$$ time complex since size of $$$A$$$ is a constant.

Method 1. using fast matrix power we can get $$$a_{3 \lfloor \frac{n}{3} \rfloor + 2}, a_{3 \lfloor \frac{n}{3} \rfloor + 1},a_{3 \lfloor \frac{n}{3} \rfloor}$$$, and $$$a_{3 \lfloor \frac{n}{3} \rfloor + n \% 3}$$$ is the answer

Method 2. It is well known that If you know the characteristic polynomial of matrix, then you can use polynomial multiplication instead of matrix product to get $$$(a_{3n+2},a_{3n+1},a_{3n},1)^T$$$ which is faster that Method 1, especially when the size of $$$A$$$ becomes bigger. Best method in general as I know (can't use NFT, since neither size of A is big nor 1,000,000,007 is NFT-friendly.)

Method 3. Note that the special $$$A$$$ can be diagonalized, thus there exist an invetible matrix $$$X$$$ such that

thus we have

We can calculate $$$X$$$ above by hand or using following SageMath Code:

A = matrix([[5,6,0,12],[3,2,0,4],[1,2,0,4],[0,0,0,1]])
A.eigenvalues()
X = A.eigenmatrix_right()[1]

Actually we can calculate $$$A^n$$$ with only 3-lines SageMath Code：

n = var('n')
A = matrix([[5,6,0,12],[3,2,0,4],[1,2,0,4],[0,0,0,1]])
A^n

and the last column of $$$A^n$$$ is

Code: 84843466

Give me five I appended k zeros at the beginning and k zeros plus 1 at the end. 83967055

thanks for your blog!