11D_Beyonder's Blog

You are given an array a consisting of nnn positive integers, numbered from 111 to nnn. You can perform the following operation no more than 3n3n3n times: choose three integers i,ji, ji,j and xxx (1≤i,j≤n;0≤x≤109)(1≤i,j≤n; 0≤x≤10^9)(1≤i,j≤n;0≤x≤109); assign ai:=ai−x⋅ia_i:=a_i−x⋅iai​:=ai​−x⋅i, aj:=aj+x⋅ia_j:=a_j+x⋅iaj​:=aj​+x⋅i. After each operation, all elements of the array should be non-negative. Can you find a sequence of no more than 3n3n3n operations after which all elements of the array a ...

简介 伸展树，英文名 Splay\text{Splay}Splay，是一种有旋的平衡树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链，它由 Daniel Sleator\text{Daniel Sleator}Daniel Sleator 和 Robert Tarjan\text{Robert Tarjan}Robert Tarjan 发明。 Splay\text{Splay}Splay 维护的信息如下。 rootrootroot tottottot fatherifather_ifatheri​ son(i,0/1)son(i,0/1)son(i,0/1) valival_ivali​ cnticnt_icnti​ SizeiSize_iSizei​ 根节点 节点数量 父亲节点 左右儿子 节点权值 权值出现次数 子树大小 伸展树的操作 函数名 1234567891011void del(int);//删除元素int Pre();//前驱int Next();//后继void splay(int);//伸展int ...

引入 沃尔什变换的数学定义 沃尔什转换矩阵 沃尔什转换矩阵为一个方阵，其阶数为 222 的幂。2k2^k2k 的沃尔什矩阵可用迭代方式产生。 起始点 k=1k=1k=1，定义 212^121 阶沃尔什转换矩阵 W2=(111−1)W_2=\begin{pmatrix}1&1\\1&-1\end{pmatrix}W2​=(11​1−1​)。假设已经有 2k2^k2k 阶沃尔什转换矩阵 W2kW_{2^k}W2k​，定义 V2k+1=(W2kW2kW2k−W2k)V_{2^{k+1}}=\begin{pmatrix}W_{2^k}&W_{2^k}\\W_{2^k}&-W_{2^k}\end{pmatrix}V2k+1​=(W2k​W2k​​W2k​−W2k​​)，再将 V2k+1V_{2^{k+1}}V2k+1​ 的列重新排列得到 W2k+1W_{2^{k+1}}W2k+1​。 在不同的应用领域，对 V2k+1V_{2^{k+1}}V2k+1​ 列的排序时，要按照不同的顺序排序。 Walsh Ordering Paley Ordering Hadama ...

简介 莫比乌斯反演是数论中的重要内容。对于一些函数 f(n)f(n)f(n)，如果很难直接求出它的值，而容易求出其倍数和或约数和 g(n)g(n)g(n)，那么可以通过莫比乌斯反演简化运算，求得 $ f(n) $ 的值。 符号及规定 1.[P]1.[P]1.[P] 是指，当 PPP 为真时，式子的值是 111；当 PPP 为假时，式子的值是 000。 2.a∣b2.a\mid b2.a∣b 是指 bbb 被 aaa 整除，即存在一个整数 kkk 使得 b=kab=kab=ka。 3.n⊥m3.n\perp m3.n⊥m 是指 nnn 与 mmm 互质，即 gcd⁡(n,m)=1\gcd(n,m)=1gcd(n,m)=1。 积性函数 定义 如果一个数论函数 $ f(n)$ 满足：当 $ x\perp y $ 时，f(xy)=f(x)f(y)f(xy)=f(x)f(y)f(xy)=f(x)f(y)，则称 f(n)f(n)f(n) 为 积性函数。 性质 若 f(x)f(x)f(x) 和 g(x)g(x)g(x) 均为积性函数，则以下函数也为积性函数： $$ \begin{aligned}h ...

题目描述 在一场战争中，战场由 nnn 个岛屿和 n−1n-1n−1 个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为 111 的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他 kkk 个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。 侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到 111 号岛屿上）。不过侦查部门还发现了这台机器只能够使用 mmm 次，所以我们只需要把每次任务完成即可。 输入格式 第一行一个整数 nnn，表示岛屿数量。 接下来 n−1n-1n−1 行，每行三个整数 u,v,wu,v,wu,v,w，表示 uuu 号岛屿和 vvv 号岛屿由一条代价为 www 的桥梁直接相连。 第 n+1n+1n+1 行，一个整数 mmm ...

引入 进行树形DP时，往往要逐个遍历树上的点进行状态转移；若树有 nnn 个节点，那么时间复杂度至少是 O(n)O(n)O(n)。 假设对某一问题进行 mmm 次询问，由于每一次都需要遍历整棵树进行树形DP，所以时间复杂度至少为 O(mn)O(mn)O(mn)。在询问次数较多的情况下，容易 TLE\text{TLE}TLE。 在处理某些问题时，原树上的一些信息是不必要的，只需要访问部分节点就可得到答案；也就是说，应当把一部分无用的节点舍去，不予访问。因此，如果能将原树的信息浓缩，将有用的信息（即应当访问的节点）保留，把大树变成小树，在小树上进行树形DP的即可降低时间复杂度。这就引入了虚树的概念。 概念 对于一棵树 T\mathrm TT，我们可以选取树上的若干个节点作为关键点，构造一棵新的树 T′\mathrm{T}'T′。要求 T′\mathrm T'T′ 包含选取的关键点和所有两个关键点的 LCA\text{LCA}LCA，且 T′\mathrm T'T′ 上的所有节点符合在 T\mathrm TT 中的祖先后代关系。满足上述条件的 T′\mathrm ...

A. Groundhog and 2-Power Representation ↬\looparrowright↬ 题目描述 Groundhog took a math class. In this class, his math teacher said, any positive integer can be represented by the power of 222. For example, 137=27+23+20137=2^7+2^3+2^0137=27+23+20. And powers are expressed in parentheses. That is, a(b)a(b)a(b) stands for aba^bab. Therefore, 137137137 can be expressed as 137=2(7)+2(3)+2(0)137=2(7)+2(3)+2(0)137=2(7)+2(3)+2(0). Further more,for 7=22+2+207=2^2+2+2^07=22+2+20 is expressed with 222, 3=2+2 ...

I. Interesting Computer Game ↬\looparrowright↬ 题目描述 Apollo is playing an interesting computer game. There are nnn rounds in the game. At each round, the computer will give Apollo two integers aia_iai​ and bib_ibi​, and Apollo can do exactly one of the following three actions. Apollo can do nothing. If integer aia_iai​ has not been selected in all previous rounds, Apollo can select integer aia_iai​. If integer bib_ibi​ has not been selected in all previous rounds, Apollo can select integer bib_ib ...

D. Fake News ↬\looparrowright↬ 题目描述 McDonald Thumb, the greatest president ever in the history of the Great Tokitsukaze Kingdom has held his 100th press conference about the global pandemic after making his 1000000th tweets with his smartphone. With a big smile on his face, Mr. Thumb said that nobody knows math more than he does. “I learn math since I was born and I am very good at it,”, said Mr. Thumb," People keep asking me why I know math so much and I sometimes find myself having those ...

B. Binary Vector ↬\looparrowright↬ 题目描述 Roundgod is obsessive about linear algebra. Let A={0,1}\mathrm A=\{0,1\}A={0,1}, everyday she will generate a binary vector randomly in An\mathrm A^nAn. Now she wonders the probability of generating nnn linearly independent vectors in the next nnn days modulo 109+710^9+7109+7. Formally, it can be proved that the answer has the form of PQ\frac{P}{Q}QP​, where PPP and QQQ are coprime and QQQ is not a multiple of 109+710^9+7109+7. The answer modulo 109+710^9+ ...