Count on a Tree II 题目描述You are given a tree with $N$ nodes. The tree nodes are numbered from $1$ to $N$. Each node has an integer weight. We will ask you to perform the following operation: $u$ $v$: ask for how many di 2018-02-11 OI > Common Skill #Lowest Common Ancestor #Depth-First-Search #Mo's Algorithm #Tree
Little Pony and Lord Tirek 题目描述Lord Tirek is a centaur and the main antagonist in the season four finale episodes in the series “My Little Pony: Friendship Is Magic”. In “Twilight’s Kingdom” (Part 1), Tirek escapes from Tartaru 2018-02-10 OI > Data Structure #Persistent #Segment Tree
Little Pony and Elements of Harmony 题目描述The Elements of Harmony are six supernatural artifacts representing subjective aspects of harmony. They are arguably the most powerful force in Equestria. The inside of Elements of Harmony can be 2018-01-29 OI > Number Theory #Fast Walsh-Hadamard Transform
The Sum of Unitary Divisors 题目描述A natural number $d$ is a unitary divisor of $n$ if $d$ is a divisor of $n$ and if $d$ and ${n \over d}$ are coprime. Let $\sigma^{\ast}(n)$ be the sum of the unitary divisors of $n$. For example, 2018-01-23 OI > Number Theory #Euler's Sieve #GCD-LCM #Dirichlet Convolution #Möbius Inversion Formula
Counting Divisors (Square) 题目描述Let $\sigma_0(n)$ be the number of positive divisors of $n$. For example, $\sigma_0(1)=1, \ \sigma_0(2)=2$ and $\sigma_0(6)=4$. Let $S_2(n)=\sum_{i=1}^n \sigma_0(i^2)$. Gi 2018-01-23 OI > Number Theory #Euler's Sieve #Prime #Dirichlet Convolution #Möbius Inversion Formula
GCD Extreme (Hard) 题目描述Let $G(n)=\sum_{i=1}^n \sum_{j=i+1}^n (i, j)$.For example, $G(1)=0, \ G(2)=(1, 2)=1, \ G(3)=(1, 2)+(1, 3)+(2, 3)=3$.Given $N$, find $G(N)$ modulo $2^{64}$. 2018-01-23 OI > Number Theory #Euler's Sieve #GCD-LCM #Dirichlet Convolution
The Child and Binary Tree 题目描述Our child likes computer science very much, especially he likes binary trees. Consider the sequence of $n$ distinct positive integers: $c_1, c_2, \ldots, c_n$. The child calls a vertex-weighted ro 2018-01-22 OI > Number Theory #Dynamic Programming #Multiplicative Inverse #Fast Fourier Transform #Generating Function #Reciprocal Polynomial #Square Root of a Polynomial
序列求和 V4 题意概述给定$n$和$k$,求$\sum_{i=1}^n i^k \bmod 10^9+7$。有$T$组数据。 数据范围:$1 \le T \le 500, \ 1 \le n \le 10^{18}, \ 1 \le k \le 50000$。 算法分析 1设答案为$f(n)$。这是一个$(k+1)$次多项式,只要确定$(k+2)$个点就可以确定$f$。 我们可以令$x=1\ 2018-01-22 OI > Number Theory #Combinatorics #Multiplicative Inverse #Fast Fourier Transform #Lagrange Interpolation Polynomial #Generating Function #Reciprocal Polynomial #Bernoulli Number
Panda's Birthday Present 题目描述On Panda’s Birthday party, he received a strange present from Jason. The present is a black box with $4$ dices in it which is used to play a game. The dice in the box is unusual. Instead of the di 2018-01-19 OI > Number Theory #Probability #Bayes' Theorem #Combinatorics
Max and Min 题目描述Two kittens, Max and Min, play with a pair of non-negative integers $x$ and $y$. As you can guess from their names, kitten Max loves to maximize and kitten Min loves to minimize. As part of this g 2018-01-18 OI > Computational Geometry #Plane Geometry #Convex Hull