Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 生成树一个无向图的生成树指的是从图中选若干边构成边集，全部点构成点集，使得这个边集加上点集恰好是一棵树。 生成树计数一个无向无权图(允许重边不允许自环)的邻接矩阵为g，显然这是一个对称矩阵，g[u][v]代表边(u,v)的重数，即若存在一条边(u,v)则g[u][v]的值为1，若存在k条，则g[u][v]的值为k。一个无向无权图(允许重边不允许自环)的度数矩阵为deg，显然这是一个对角矩阵，deg[u][u]代表点u的度数。一个无向无权图(允许重边不允许自环)的基尔霍夫矩阵(拉普拉斯矩阵)为hoff，是度数矩阵减去邻接矩阵。矩阵树定理说一个无向图的生成树的个数刚好等于基尔霍夫矩阵的行列式的任意n-1阶主子式(代数余子式)的行列式的绝对值。生成树计数复杂度$O(V^3+E)=O(V^3)$黑暗前的幻想乡我们利用矩阵树定理就能轻松解决 黑暗前的幻想乡代码 最小生成树有 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial nameEasy Math Problem descirptionOne day, Touma Kazusa encountered a easy math problem. Given n and k, she need to calculate the following sum modulo $1e9+7$.$$∑_{i=1}^n∑^n_{j=1}gcd(i,j)^klcm(i,j)[gcd(i,j)∈prime]%(1e9+7) $$However, as a poor student, Kazusa obviously did not, so Touma Kazusa went to ask Kitahara Haruki. But Kitahara Haruki is too busy, in order to prove that he is a skille ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial min25筛是什么min25筛是一种筛法，他能以亚线性的时间复杂度筛出一类函数的前缀和 定义一部分符号$M(x) x\gt1$代表$x$的最小质因子 我们再设$P_j$为第$j$小的质数, $P_1=2,P_2=3,P_3=5…$ 先看最简单的第一类函数$$\begin{aligned}f(x)=\left{\begin{matrix}x^k&x\in primes\0&x \notin primes\end{matrix}\right.\end{aligned}$$对于这个函数我们可以利用min25筛来达到$O(\frac{n^\frac{3}{4}}{lg(n)})$的时间复杂度，我们没有办法直接求这个函数的前缀和，但是我们可以另外设一个相对好求的函数$h(x)=x^k$，通过h来求f，因为$\begin{a ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 中间结论$$f_n = \sum_{i=0}^n (-1)^i {n \choose i} g_i\Leftrightarrowg_n = \sum_{i=0}^n (-1)^i {n \choose i} f_i$$ $$f_n = \sum_{i=0}^n {n \choose i} g_i\Leftrightarrowg_n = \sum_{i=0}^n (-1)^{n-i} {n \choose i} f_i$$ 杜教筛$$g(1)\sum_{i=1}^nf(i)=\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)$$ 数论变换$$\begi ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###name种花家的零食 ###descirption在很久以前，有一颗蓝星，蓝星上有一个种花家。种花家有1到n共n包零食，同时种花家的兔子又有1到n共n个朋友(比如毛熊，鹰酱，脚盆鸡等）。昨天，兔子的n个朋友都到他家来玩了。他的n个朋友瓜分了他的n包零食，每个人都恰好吃了一包零食，没有两个人吃了同一包零食。兔子发现，第i个朋友吃第j包零食能获得的愉悦值是$i\mod j$。今天，兔子想回忆起每个朋友吃的是哪包零食，他想不起来了，但是他却记得了所有人的愉悦值之和s。于是，兔子找上了你，请你构造出一种可能的方案。由于兔子记忆力不好，他有可能记错了s，所以可能会存在无解的情况。 ###input一行两个整数$n(1\leq n\leq 10^6)$和$s(1\leq s\leq10^{18})$ ###output如果不存在满足条件的方案，输出一行-1。否则输出n行，每行一个整数，第i行的整 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 有这样一类问题，他们的形式常常是这个样子$$\begin{aligned}\sum_{i=1}^n{f(i)[gcd(i,j)=1]}\end{aligned}$$ 我们来对他进行变形$$\begin{aligned}&\sum_{i=1}^n{f(i)[gcd(i,j)=1]}\=&\sum_{i=1}^n{f(i)e(gcd(i,j))}\=&\sum_{i=1}^n{f(i)(\mu1)(gcd(i,j)}\=&\sum_{i=1}^n{f(i)\sum_{d|gcd(i,j)}\mu(d)}\=&\sum_{i=1}^n{f(i)\sum_{d|i,d|j}\mu(d)}\=&\sum_{d|j}{\mu( ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###namearray ###descirptionYou are given an array $a_1,a_2,…,a_n(∀i∈[1,n],1≤a_i≤n)$. Initially, each element of the array is unique. Moreover, there are m instructions. Each instruction is in one of the following two formats: (1,pos),indicating to change the value of $a_{pos}$ to $a_{pos}+10,000,000$; (2,r,k),indicating to ask the minimum value which is not equal to any $a_i$ ( 1≤i≤r ) and not less ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###name ###descirption ###input ###output ###sample input ###sample output ###toturial先来看一个简单的变形$$\begin{aligned}&\sum_{i=1}^{n}gcd(x,i)\=&\sum_{d|x}\sum_{i=1}^{n}[gcd(x,i)=d]\=&\sum_{d|x}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[gcd(\frac{x}{d},i)=1]\=&\sum_{d|x}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y|\frac{x}{d},y|i}\mu(y)\=&am ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###nameString ###descirptionTom has a string containing only lowercase letters. He wants to choose a subsequence of the string whose length is k and lexicographical order is the smallest. It’s simple and he solved it with ease.But Jerry, who likes to play with Tom, tells him that if he is able to find a lexicographically smallest subsequence satisfying following 26 constraints, he will not cause Tom ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###nameMeteor ###descirptionhough time passes, there is always someone we will never forget.“The probability of being hit by a meteor is one in a billion, but it is much more miraculous, to meet you in my life.” said Tom to Jerry with affection.“One in a billion? I may not agree with you.” answered Jerry proudly, “Let’s do the math.”…Thinking of the days they have happily spent together, Tom can’t h ...