https://atcoder.jp/contests/abc129/tasks/abc129_eI solved it by digit DP with ordering monoid. In this DP, we scan the digits from the lowest to the highest as maintaining (order, carry). Iwarete mireba a+b=(a^b)+2*(a&b) kizuku beki. #incl…

https://codeforces.com/contest/1172/problem/EHL decomposition. https://codeforces.com/contest/1172/submission/55290873

https://codeforces.com/contest/392/problem/DLet \(f_A(k)\) be the minimum i such that \(A_i=k\). If there doesn't exist such a index, we define \(f_A(k) = \infty\). \(f_B(k)\) and \(f_C(k)\) are similarly defined. Then, we want to obtain t…

https://atcoder.jp/contests/agc034/tasks/agc034_fLet a and b be arrays with 2^n elements. a*b denotes the xor convolution of a and b.Let x=[x[0], x[1], ... , x[2^n-1]] be the answer and p=[p[0],...,p[2^n-1]] be the probability that i-th el…

https://atcoder.jp/contests/abc127/tasks/abc127_fMaintain the first smallest half of a[i] and the second smallest half of a[i], call them L and R respectively. Then, the answer is sum(R)-sum(L) if L and R have the same number of elements.T…

https://codeforces.com/contest/1158/problem/AI didn't know the iterator has operator[] *1. I found this when I read his solution. #include <vector> #include <cassert> using namespace std; int main() { vector<int> a{1,2,3,4,5}; assert(a.begin()[0] == 1); assert(</int></cassert></vector>…

I - リスのお仕事 Let us consider a graph whose vertices are (vertex ID, The cost used at last). If there exists a vertex having a lot of kinds of costs, it is difficult to update the distance efficiently. To perform efficiently, we prepare…

https://codeforces.com/contest/1153/problem/FWithout loss of generality, we assume \(L=1\). The probability that x is covered by a single interval is \(2x(1-x)\). Let \(f(x)=2x(1-x)\), then the expectation of the length covered by exactly …

Pylons If we properly take some k, (i,j) -> ((i+k)%H,j+1) -> ((i+2k)%H,j+2) -> ... is a path satisfying the given conditions. I don't have any proof, but at least under this constraints, it is correct. In addition, (H,W)=(4,4) doesn't work…

https://codeforces.com/contest/1119/problem/H Preliminaries Hadamard transform of 3bits is almost the same as Fourier transform of 2*2*2. A polynomial of x,y,z can be represented as 8 coefficients of 1,x,y,z,xy,xz,yz,xyz. Hadamard transfor…

D Using binary representation, we can determine the missing numbers. Someone may think 10 bits are necessary, but 5 bits are sufficient. 4 bits are also ok?For simplicity, we explain the solution for small cases. We send the following 10 s…

https://yukicoder.me/problems/no/3046(First solution) M denote the maximum value of A. Then, the answer is\[ [x^{M - 1}] (x^{M + K - 1} \bmod (x^{M}-x^{M - a_1}-\cdots - x^{M-a_N})). \]https://yukicoder.me/submissions/334973(Second solutio…

Draw parabolas satisfying the given condition. Then, an envelope appears *1.This is similar to the convex hull. Actually, Graham scan *2 also works in this case. There is another solution using the the convex hull of (x[i],y[i]-x[i]*x[i]).…

https://atcoder.jp/contests/exawizards2019/tasksDynamic programming. Look at the elements in ascending order.Let dp[i][j] be the answer of the sub problem replacing a[0],...,a[N-1] with a[0],...,a[i-1] and replacing X with j. Suppose a[0] …

题目链接 https://codeforces.com/contest/1139/problem/Df(k) 表示 a[1],...,a[k] 的最大公约数不是 1 的概率。然后答案是 1+f(1)+f(2)+f(3)+...。a[1],...,a[n] 的最大公约数是 1 和 a[1],...,a[k] 不能被 2,3,4,... 整除等价。所以由容斥原理可以计算 f(k…

https://yukicoder.me/problems/no/803Once we realize this problem is related to a system of linear equations, this problem has been almost solved. All we have to do is to find the number of solutions of the given linear system.Let u be a so…

https://yukicoder.me/problems/no/802Let us find the number of \(x_1, \ldots, x_N\) such that \(x_1 + \cdots + x_N \le M\) and \( x_1 \ge 0\), \(0 \le x_i \le D_2-D_1 \) for \(2\le i \le N\). The generating function can be written as\begin{…

https://atcoder.jp/contests/agc031/tasks/agc031_dThis article is almost the same as the official editorial. I just want to write English and Chinese (A month has passed since I started learning Chinese. If you cannot read my Chinese, I'm s…

https://codeforces.com/contest/1136/problem/EIf we have a segment tree which can perform the following operations, we can directly solve this problem.1. For $l \le i \le r$, $A_i \gets \max(A_i, x)$ 2. For $l \le i \le r$, $A_i \gets A_i +…

https://atcoder.jp/contests/wupc2019/tasks/wupc2019_fThe solution is easy for us, so I do not explain it here. Instead, I shall explain how to reduce the vertex cover problem to the minimum st cut problem. This technique is also known as K…

https://codeforces.com/contest/1132/problem/BI was going to solve all the problems by Rust. But, I lost the motivation due to TLE in the problem B. I rewrite the I/O after the contest, then my solution becomes faster than the C++'s one. I'…

https://codeforces.com/contest/1137/problem/C We do not need to use GCD or something. We prepare the graph with N×D vertices and do SCC on it. Then, we can do dynamic programming on the contracted graph. The total time complexity is O(ND),…

Problem Link: https://codeforces.com/contest/1137/problem/BThere are a lot of ways to solve this problem. For example, we can use Z-algorithm, rolling hash and suffix array (suffix array might be too slow for this constraints). This proble…

https://codeforces.com/contest/1132/problem/EUsing a technique like digit-dp, this problem can be reduced to the 0-1 problem. I define the table dp[2000][1 My implementation is a little noisy. https://codeforces.com/contest/1132/submission…

https://codeforces.com/contest/1116I solved 11 problems. The remaining two problems are difficult for me. B1 Let us create a function which converts |000> to the first state, say f. We only have to apply (Adjoint f) to the given state. We …

This article is written for my future self. The following explanation isn't clear.Official solutions are here https://assets.codeforces.com/rounds/1115/warmup-editorial.pdf. Some of them use useful functions, especially G2 and U3. I’ll rev…

An optimal move is like this.Fix the start vertex r. The red route is better than the orange one. In general, if the maximum weight of the edges on the r-v path is greater than the weight of the edge between v and parent(v), then v is unne…

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_f The orange course is shorter than the black one. The orange course is shorter than the black one. Therefore, points on the orange area are unnecessary after this move. P…

https://codeforces.com/contest/1114/problem/FMy solution is the fastest on Feb 16, 2019. The discrete logarithm is one of the keys for speed. (This approach is based on deja-vu's solution.)https://codeforces.com/contest/1114/submission/499…

Problem https://codeforces.com/contest/1114/problem/E Solution https://codeforces.com/blog/entry/65136We can find a[0]. Generating random values between 0 and n-1, then d=gcd(a[r[0]] - a[0], a[r[1]] - a[0], ... , a[r[29]] - a[0]) become th…