传送门 由于是边权三进制不进位的相加,那么可以考虑每一位的贡献 对于每一位,生成树的边权相当于是做模 \(3\) 意义下的加法 考虑最后每一种边权的生成树个数,这个可以直接用生成函数,在矩阵树求解的时候做一遍这个生成函数的模 \(3\) 意义下的循环卷积求出系数即可 暴力多项式运算不可取 考虑选取 \(3\) 个数字 \(x_i\),使得 \(x_i^3\equiv1(mod~10^9+7)\) 即找出 \(3\) 次单位复数根 \(\omega_3^0,\omega_3^1,\omega_3^

loj6271 「长乐集训 2017 Day10」生成树求和 加强版(矩阵树定理,循环卷积) loj 题解时间 首先想到先分开三进制下每一位,然后每一位分别求结果为0,1,2的树的个数. 然后考虑矩阵树求出来的是树的边权之积的和,而我们要求树的边权的不进位三进制和的和. 由于矩阵树求出来的是树的边权之积的和,考虑暴力上生成函数求解循环卷积,结果就是 $ c $ 的项的系数和. 但很明显生成函数暴力算是没得整的. 所以我们想到了利用单位根实现的k进制FWT. 很幸运的 $ \omega_{ 3 }

又是一个矩阵树套多项式的好题. 这里我们可以对每一位单独做矩阵树,但是矩阵树求的是边权积的和,而这里我们是要求加法,于是我们i将加法转化为多项式的乘法,其实这里相当于一个生成函数?之后如果我们暴力做的话,就是强行带入x插值,复杂度$O(8*2n*n^{3})$,还不够优秀,于是我们考虑用$dft$优化这个过程,这里我们需要找到一个三次单位根,于是我们考虑扩域的思想,我们把数表示为$(a+b*w_{3})$,这里$w_{3}$满足$w_{3}^{3}=1$且$w_{3}^{1}+w_{3}^{2}

「长乐集训 2017 Day10」划分序列 题目描述 给定一个长度为 n nn 的序列 Ai A_iA​i​​,现在要求把这个序列分成恰好 K KK 段,(每一段是一个连续子序列,且每个元素恰好属于一段),并且每段至少有一个元素,使得和最大的那一段最小. 请你求出这个最小值. 输入格式 第一行两个整数 n,K n, Kn,K,意义见题目描述.接下来一行 n nn 个整数表示序列 Ai A_iA​i​​. 输出格式 仅一行一个整数表示答案. 样例 样例输入 9 4 1 1 1 3 2 2 1 3

题目描述 村子间的小路年久失修,为了保障村子之间的往来,AAA君决定带领大家修路. 村子可以看做是一个边带权的无向图GGG, GGG 由 nnn 个点与 mmm 条边组成,图中的点从 1∼n1 \sim n1∼n 进行编号.现在请你选择图中的一些边,使得 ∀1≤i≤d\forall 1 \leq i \leq d∀1≤i≤d , iii 号点和 n−i+1n - i + 1n−i+1号点可以通过你选择出的那些边连通,并且你要最小化选出的所有边的权值和.请你告诉AAA君这个最小权值和. 输入格式

题目 对于两个区间\((a,b),(c,d)\),若\(c < a < d\)或\(c < b < d\)则可以从\((a,b)\)走到\((c,d)\)去,现在有以下两种操作: 给定\(1 \space x \space y\),表示在集合中添加\((x,y)\)这个区间,保证新加入的这个区间一定比之前的所有区间长度长. 给定\(2 \space a \space b\),表示询问是否有一条路径能从第\(a\)个区间走到第\(b\)个区间. 初始时区间集合为空,现在请你回答所有的

[题目大意] 一个合法的引号序列是空串:如果引号序列合法,那么在两边加上同一个引号也合法:或是把两个合法的引号序列拼起来也是合法的. 求长度为$n$,字符集大小为$k$的合法引号序列的个数.多组数据. $1 \leq T \leq 10^5, 1 \leq n \leq 10^7, 1\leq k \leq 10^9$ [题解] 显然引号序列可以看做括号序列,于是我们有了一个$O(n^2)$的dp了. 设$f_{i,j}$表示到第$i$个位置,前面有$j$个左引号没有匹配,的方案数 每次,要么有

题面 传送门 题解 首先可以用一个矩形去套这个多边形,那么我们只要枚举这个矩形的左下角就可以枚举完所有多边形的位置了 我们先对每一个\(x\)坐标开一个\(bitset\),表示这个\(x\)坐标里哪些\(y\)坐标处有苍蝇.然后再处理出矩形中哪些位置会被覆盖,这个同样可以枚举\(x\)坐标,然后对于所有线段,如果它穿过这个\(x\)坐标,就用一个\(stack\)存起来,然后把所有\(stack\)里的\(sort\)一下,乱搞就好了(具体可以看代码) 注意只有一条线段完全穿过\(x\)才有可

题面 传送门 题解 这么简单一道题我考试的时候居然只打了\(40\)分暴力? 如果我们把每个点的\(a_i\)记为\(deg_i-1\),其中\(deg_i\)表示有\(deg_i\)个数的\(A_i\)是\(i\),那么很明显所有数的\(a_i\)之和为\(0\) 于是,必然存在一个点\(k\),满足从\((k,k+1)\)把环断掉之后,且以\(k+1\)为开头,整个数列的前缀和不小于\(0\),也就是说精灵永远不会跨过\(k\)去找别的侏儒打架 这个\(k\)的话,只要找到前缀和最小值的地方

题面 传送门 题解 我的做法似乎非常复杂啊-- 首先最长上升子序列长度就等于把它反过来再接到前面求一遍,比方说把\(2134\)变成\(43122134\),实际上变化之后的求一个最长上升子序列和方案数就是答案了 最长上升子序列随便求求,主要是这个方案数很麻烦啊--我的做法是对每一个长度开一个动态开点线段树,然后每次在对应的长度里二分跑前缀和 其实这里完全不用动态开点线段树的,直接把权值离散一下然后一棵线段树就够了,跑得飞快 其实这里连线段树都不需要直接树状数组就可以维护前缀最大值和方案之和了

[题目大意] 给出一个$n$个数的序列$\{a_n\}$,其中有些地方的数为0,要求你把这个序列填成一个1到$n$的排列,使得: $(a_i, a_j) = 1$,当且仅当$(i, j) = 1$.多组数据. $n \leq 3\times 10^5, T\leq 10$ CodeForces:无多组数据,$n \leq 10^6$ [题解] 这题有点神奇啊.. 首先考虑序列全是0要怎么做. 考虑到如果两个数的位置含有的因数种类完全一样,那么它们是可以互换的.(这个挺显然的) 观察如果两个质数的

传送门 Description 有一天,小 A 的母亲对他家里的卫生状况非常不满意,他的房间里有非常多的苍蝇.在母亲的威逼利诱下,小 A 拿起了苍蝇拍去消灭家里的苍蝇.然而,小 A 以前从来没有亲手消灭过任何一只苍蝇,以至于在他拿起苍蝇拍的那一刻,他对苍蝇起了怜悯之心 -- 他不想伤害任何一只苍蝇.现在,小 A 面前的窗户上有 只苍蝇,他想知道有多少种方式可以在他拿起苍蝇拍拍窗户的时候,不伤害任何一只苍蝇. 窗户可以看作是一个左下角位于坐标系原点的矩形,苍蝇拍可以看作是一个多边形.在小 A 向窗

Loj 2320.「清华集训 2017」生成树计数 题目描述 在一个 \(s\) 个点的图中,存在 \(s-n\) 条边,使图中形成了 \(n\) 个连通块,第 \(i\) 个连通块中有 \(a_i\) 个点. 现在我们需要再连接 \(n-1\) 条边,使该图变成一棵树.对一种连边方案,设原图中第 \(i\) 个连通块连出了 \(d_i\) 条边,那么这棵树 \(T\) 的价值为: \[ \mathrm{val}(T) = \left(\prod_{i=1}^{n} {d_i}^m\right)

LOJ_6045_「雅礼集训 2017 Day8」价 _最小割 描述: 有$n$种减肥药,$n$种药材,每种减肥药有一些对应的药材和一个收益. 假设选择吃下$K$种减肥药,那么需要这$K$种减肥药包含的药材也等于$K$时才会有效果. 求最小收益,收益可能是负的.保证有完美匹配. 分析: 先把所有权值取相反数求最大收益,因为最小收益看着很难受. $S$->减肥药($inf$+收益),减肥药->药材($inf$),药材->$T$($inf$). 然后求最小割,答案就是$S$连出去的边的容量和

Loj #2331. 「清华集训 2017」某位歌姬的故事 IA 是一名会唱歌的女孩子. IOI2018 就要来了,IA 决定给参赛选手们写一首歌,以表达美好的祝愿.这首歌一共有 \(n\) 个音符,第 \(i\) 个音符的音高为 \(h_i\).IA 的音域是 \(A\),她只能唱出 \(1\sim A\) 中的正整数音高.因此 \(1\le h_i\le A\). 在写歌之前,IA 需要确定下这首歌的结构,于是她写下了 \(Q\) 条限制,其中第 \(i\) 条为:编号在 \(l_i\) 到

Loj #2324. 「清华集训 2017」小 Y 和二叉树 小Y是一个心灵手巧的OIer,她有许多二叉树模型. 小Y的二叉树模型中,每个结点都具有一个编号,小Y把她最喜欢的一个二叉树模型挂在了墙上,树根在最上面,左右子树分别在树根的左下方与右下方,且他们也都满足 这样的悬挂规则.为了让这个模型更加美观,小Y选择了一种让这棵二叉树的中序遍历序列最小的悬挂方法.所谓中序遍历最小,就是指中序遍历的结点编号序列的字典 序最小. 一天,这个模型不小心被掉在了地上,幸运的是,所有结点和边都没摔坏,但是她想

Loj #2321. 「清华集训 2017」无限之环 曾经有一款流行的游戏,叫做 *Infinity Loop***,先来简单的介绍一下这个游戏: 游戏在一个 \(n \times m\) 的网格状棋盘上进行,其中有些小方格中会有水管,水管可能在方格某些方向的边界的中点有接口,所有水管的粗细都相同,所以如果两个相邻方格的公共边界的中点都有接头,那么可以看作这两个接头互相连接.水管有以下 \(15\) 种形状: 游戏开始时,棋盘中水管可能存在漏水的地方. 形式化地:如果存在某个接头,没有和其它接头

「雅礼集训 2017 Day7」事情的相似度 题目链接 我们先将字符串建后缀自动机.然后对于两个前缀\([1,i]\),\([1,j]\),他们的最长公共后缀长度就是他们在\(fail\)树上对应节点的\(lca\)的\(maxlen\). 所以现在问题就变成了一个树上问题:给定一棵树,每个点有一个权值\((mxlen)\),询问编号在一段区间内的点两两之间\(lca\)权值的最大值. 方法很多,这里用的\(dsu\ on\ tree\).对于每个点\(v\),我们计算其作为\(lca\)的贡献

「雅礼集训 2017 Day2」水箱 我怎么知道这种题目都能构造树形结构. 根据高度构造一棵树,在树上倍增找到最大的小于约束条件高度的隔板,开一个 \(vector\) 记录一下,然后对于每个 \(vector\) 按照高度排序一下,树形 \(dp\) 即可 \(Code\ Below:\) #include <bits/stdc++.h> #define pii pair<int,int> #define mp make_pair #define F first #define

「雅礼集训 2017 Day1」市场 挺神仙的一题.涉及区间加.区间除.区间最小值和区间和.虽然标算就是暴力,但是复杂度是有保证的. 我们知道如果线段树上的一个结点,\(max=min\) 或者 \(max=min+1\) 并且 \(d|max\),是可以直接剪掉的. 我们定义线段树上一个结点的势能为 \(\log(max-min)\),那么我们每执行一次区间除,都会引起势能的减小. 但是执行区间加时我们涉及 \(\log n\) 个结点,最差情况下会将它们的势能恢复为 \(\log(max-m