- 博客(1140)
- 收藏
- 关注
RSS订阅
原创 杂题收录+简要题解4
hdu 6868 Absolute Math令 f(n)=∑d∣n∣μ(d)∣f(n)=\sum_{d|n}|\mu(d)|f(n)=∑d∣n∣μ(d)∣。每次给定 n,mn,mn,m，求∑i=1mf(ni)\sum_{i=1}^mf(ni)i=1∑mf(ni)n,m≤107,T≤104n,m\le 10^7,T\le 10^4n,m≤107,T≤104注意到 f(n)=2ω(n)f(n)=2^{\omega(n)}f(n)=2ω(n)，其中 ω(n)\omega(n)ω(n) 表示 nnn
2020-08-19 07:47:03
559
原创 杂题收录+简要题解3【杭电多校】
hdu 6756 Finding a MEX给一个无向图，点有点权。每次修改一个点的点权，或询问与某个点相连的所有点的点权的mex。n,m,q≤105n,m,q\le 10^5n,m,q≤105把点按照度数是否大于 n\sqrt nn 分类，称为小点和大点。对每个大点用分块维护mex。修改点权时，维护相连的大点的答案。询问时，小点暴力询问，大点分块询问。hdu 6760 Math is Simple给出 nnn，计算∑1≤a<b≤n,gcd(a,b)=1,a+b≥n1ab\sum_
2020-07-21 21:21:14
876
2
原创 杂题收录+简要题解2
洛谷P6158 封锁给出一个n∗nn*nn∗n的网格图，每条边有两个边权。求一个左上角到右下角的割使得（第一个边权之和）∗（第二个边权之和）（第一个边权之和）*（第二个边权之和）（第一个边权之和）∗（第二个边权之和）最小。n≤400n\le 400n≤400跟最小乘积生成树的做法类似，把每种方案看成二维平面上的一个点(∑x,∑y)(\sum x,\sum y)(∑x,∑y)，其中x,yx...
2020-03-01 22:45:22
660
原创 杂题收录+简要题解1
hdu 6312 Game有一个集合S={1,…,n}S=\{1,\dots,n\}S={1,…,n}，两个人轮流操作，每次可以选走集合中的一个数和它的所有约数，问先手是否必胜。T≤10,n≤500T\le10,n\le500T≤10,n≤500结论是先手必胜。若局面S′={2,…,n}S'=\{2,\dots,n\}S′={2,…,n}是先手必胜，则先手可用同样的方式...
2019-08-13 09:52:04
767
原创 superguymj的thuwc2019游记
thuwc2019游记(我是superguymj，因为没有blog，所以就发到这来了。感谢beginend的友情铺位)day0晚上日常上分之后有点兴奋，结果十点多躺在床上睡不着，起来听了会儿歌就已经12点了。day1早上七点多起的，感觉并不是很困。驾车到达广二是9点多，根据指引找到了报道处。这次有四种颜色的衣服，都是外套，分别是红蓝灰黑。但每个人只能拿一件。我还没说话，工作人员就塞了一件...
2019-01-26 19:33:52
2419
12
原创 【笔记】混合(纯)纳什均衡与PPAD(PLS)完全
参考CS364A的Lecture Note #19和#20.纯纳什均衡与 PLSPLSPLS 完全局部搜索问题 (Local Search Problems)最大割问题最大割问题是研究局部搜索问题的经典问题. 给定一个无向图 G=(V,E)G=(V,E)G=(V,E), 每条边有非负边权 we≥0w_e\ge 0we≥0. 目标是找到 VVV 的一个分割 (S,S‾)(S,\overline{S})(S,S), 其中 SSS 和 S‾\overline{S}S 均非空, 使得两个端点分别位于 SS
2022-01-17 17:38:52
1596
1
原创 【笔记】非完全信息下的动态博弈（序贯均衡）
来源于mit的Economic Applications of Game Theory这门课的Lecture Notes的第16章。序贯均衡考虑如下博弈：员工有 0.70.70.7 的概率是勤奋的，0.30.30.3 的概率是懒惰的。公司可以选择雇佣或者不雇佣该员工；若雇佣，则员工可以选择工作或偷懒。注意到加粗的线表示了一个贝叶斯纳什均衡（Bayesian Nash equilibrium），这显然不是我们想要的结果。为了解决这个问题，不妨设员工是序贯理性（sequentially rational
2021-12-30 22:23:39
3777
原创 【论文阅读】The Simple Economics of Optimal Auctions
前言这篇文章讨论了价格歧视垄断的模型，并为该模型找到了解决方案。之后说明了该模型与 Myerson 的论文 Optimal Auction Design 里的最优拍卖模型是等价的。这个模型的转换从另一个角度描述了拍卖模型中的最优策略，将其与一些经济学中的概念联系了起来，从而能够有更直观的理解，也为之后对 Myerson 拍卖的分析找到了更简单的模型。解决最优拍卖问题的方法首先介绍一下拍卖模型，以及在证明了该模型与价格歧视垄断模型的等价性后，最优拍卖问题的解决方法。假设有 nnn 个买家和一件物品。物
2021-12-30 15:16:10
804
原创 【论文阅读】Send Mixed Signals – Earn More, Work Less
Abstract考虑多类型的单物品拍卖，且所有买家的价值已知，并假定使用二价拍卖。文章说明了混合信号策略比纯信号策略收益更高，给出了计算最优混合信号策略的线性规划，并将其变量数降至多项式级别，因此能在多项式时间内求解。同时证明了使用最优信号策略的收益对某个指标有很好的近似比。证明中利用了混合信号策略等价于多个可分割物品拍卖的性质。Motivation在信息不对称的情形下，即卖家拥有私有信息，为了最大化自己的收益，卖家通过信号的形式透露部分信息是很合理的方式。相较于纯信号策略，显然使用混合的信号策略效果
2021-12-13 10:30:45
498
原创 【笔记】凸优化1
b站凌青老师凸优化课程1-6课笔记。什么是优化优化就是从一个可行解的集合中，寻找出最优的元素。写成数学形式：minimize f0(x)subject to fi(x)≤bii=1,⋯ ,M\begin{aligned}&\text{minimize }f_0(x)\\&\text{subject to }f_i(x)\le b_i\quad i=1,\cdots,M\end{aligned}minimize f0(x)subjec
2021-12-11 18:49:46
526
原创 【论文阅读】Optimal Advertising for Information Products
Abstract这篇是发表在 EC21 上的文章。考虑的情形是有一个不可知的状态，买家能够选择一个行动，其收益取决于状态和行动。卖家知道真实的状态，想要将状态信息出售给买家。为了让买家愿意付钱购买，卖家可以先免费透露部分信息给买家，改变其对状态的估计，从而让其购买状态信息。买家和卖家都想最大化自己的收益。论文里讨论了卖家的最优机制设计问题，通过优化的角度，给出了特殊情形下问题的解法，同时证明了一般情形下该问题是 NP 难的。由于论文里涉及到较多凸优化的知识，所以只读懂了一部分。希望等之后学了凸优化之后再
2021-12-09 22:51:47
413
原创 【牛客多校20210719 Olefin】【计数、分治FFT】
(我是superguymj，因为没有blog，所以就发到这来了。感谢beginend的友情铺位)简单题意给定一个长度为 nnn 的 010101 串，每次翻转一个两端为 111 的交替段。求连续翻转kkk次的方案数（保证没有连续的 111）。题解显然，由连续多个 000 隔开的 010101 交替段之间互相独立，因此只需考虑 111 的个数为 nnn 的交替串连续翻转 0 n0~n0 n 次的方案数，然后卷起来即可。一次操作可以看成一个区间，那么区间之间只能嵌套不能包含，并且后
2021-07-22 18:17:28
280
原创 【牛客多校20210717 Cut the Tree】【长链剖分】
(我是superguymj，因为没有blog，所以就发到这来了。感谢beginend的友情铺位)简单题意给一颗树，定义 f(x)f(x)f(x) 为删除点 xxx 后的森林的树上最长上升子序列，求最小的 f(x)f(x)f(x)。题解题解看不懂，时间复杂度还劣，所以自己写一篇。首先考虑如何算子树内的树上最长上升子序列。经典做法是维护一个上升和下降的单调栈，每次合并就是把两个单调栈点积取 min/max。注意单调栈的长度是 O(depth)O(depth)O(depth) 的，所以长剖即可。复杂度
2021-07-20 21:16:28
363
2
原创 拟阵学习小记
拟阵简介拟阵理论可用于判断一个问题能否通过贪心策略求解，或者说用于证明一个贪心策略是否正确。其能够涵盖许多用贪心法求解的问题，但不是所有的贪心算法都符合拟阵理论。拟阵的定义称一个有序对 M=(S,L)M=(S,L)M=(S,L) 为拟阵，如果它满足以下条件：有穷：SSS 是一个有穷集合。遗传性：LLL 为 SSS 的一个非空子集组成的集合，满足如果 B∈LB\in LB∈L 且 A⊆BA\subseteq BA⊆B，那么 A∈LA\in LA∈L。称 LLL 的元素为独立子集。显然空集 ∅∈L\
2021-04-07 19:43:48
311
2
原创 最大最小堆（min-max heap）
做项目的时候听说了最大最小堆这种数据结构，于是就来学习一下。最大最小堆算是二叉堆的变形，结构与二叉堆类似，只是节点的排列顺序有所不同。相较于二叉堆，最大最小堆能够同时支持最大值或最小值的查询（O(1)O(1)O(1)）和删除（O(logn)O(\log n)O(logn)）操作。相较于用两个二叉堆或用平衡树实现相同的功能，最大最小堆唯一的优势大概就是只需要开一个大小为 nnn 的数组。性质最大最小堆的结构和二叉堆一样，都是一棵满二叉树。若令根节点深度为 000，则满足在以深度为偶数的节点为根的子树
2021-02-19 00:34:18
1848
原创 可持久化可并堆优化k短路
问题对于带权有向图，定义路径的长度为经过的边的权值之和。两条路径不同当且仅当经过边的顺序不同。给一个带权有向图 GGG 以及起点和终点 s,ts,ts,t，求 GGG 中 sss 到 ttt 权值前 kkk 小的路径。朴素做法问题转化定义 disxdis_xdisx 表示从 xxx 到 ttt 的最短路长度，权值为 www 的边 e:u→ve:u\to ve:u→v 的花费 δ(e)=disv−disu+w\delta(e)=dis_v-dis_u+wδ(e)=disv−disu+w可以理解
2021-02-13 12:29:02
469
原创 红黑树学习小记
红黑树的形态红黑树是一棵带拓展节点的平衡二叉树，即某个节点若没有左儿子，则新建一个拓展节点作为左儿子。右儿子同理。拓展节点称为外部节点，其余节点称为内部节点。每个节点被染成红色或黑色。其中根节点必然是黑色。外部节点必然是黑色。内部节点可以是红色或黑色。需要满足的性质：每个红色节点的两个儿子必然都是黑色节点，即不存在两个相邻的红色节点。对于任意一个节点，从它出发到其子树内的所有外部节点的路径上的黑点数量均相同。称从节点 XXX 出发，到其子树内任意一个外部节点路径上的黑点数量为 XX
2021-01-05 22:08:19
346
原创 B树、B+树学习小记
B树B树和二叉查找树类似，均是通过把数据储存成树的形态，支持数据的动态查找、插入和删除。不同于二叉查找树，B树是一棵多路树，也就是每个节点可以有若干儿子。这样在查找的时候，读取内存的次数就会大大降低，从而提高查找的效率。B树的形态对于取定的参数 mmm：B树是一棵多路树，每个节点最多有 mmm 个儿子。除了根节点和叶节点以外，每个节点最多有 ⌈m2⌉\lceil\frac{m}{2}\rceil⌈2m⌉ 个儿子。若根节点有儿子，则至少有两个儿子。所有叶子节点都有相同的深度。有 kkk 个
2021-01-05 11:33:47
168
原创 【线性平面图判定算法】
最近去看了Hopcroft和Tarjan老爷子在1974年提出的 O(V)O(V)O(V) 时间内判断一个图是否是平面图的算法，这是原文。用了好一些时间才完全理解整个算法。想懂之后其实并不难，但真真实实非常巧妙，代码实现并不复杂，常数也不算大。不知道为什么网上基本找不到科普文。一些记号简单路径：每个点至多被经过一次。环：除起点外，每个点至多被经过一次。割点：删掉该点后原图不再连通。双连通图：连通且不包含割点的图。p:v⇒∗wp:v\Rightarrow ^* wp:v⇒∗w：ppp 是一条从
2020-12-12 00:32:17
2363
2
原创 【洛谷 6789 寒妖王】【状压dp】
题意给一个 nnn 个点 mmm 条边的简单无向图，边有边权。定义一个边集是好的，当且仅当将这些边和与这些边相连的点取出来形成的图没有两个或以上处在同一个连通块的不同的环。同时定义一个边集的权值为边集中所有边的边权之和。每条边有 50%50\%50% 的概率消失，问图中权值最大的好边集的权值的期望。n≤15,m≤60n\le 15,m\le 60n≤15,m≤60分析实际上就是问最大生成环套树森林的期望。考虑按边权从大到小加边，一条边有贡献，当且仅当其两个端点位于的连通块是一棵树，或位于不同的连通
2020-08-24 08:14:18
525
1
原创 【NOI2020 超现实树】
题意对于所有的无标号且区分左右儿子的有根二叉树，定义一棵树 T1T_1T1 可以由另一棵树 T2T_2T2 生长得到，当且仅当可以通过进行若干次将 T2T_2T2 的叶节点替换成某棵二叉树的操作得到。对于一个二叉树集合 T\mathscr{T}T，定义 grow(T)\mathrm{grow}(\mathscr{T})grow(T) 表示所有可以由 T\mathscr{T}T 中的树生长得到的树构成的集合。定义 grow(T)\mathrm{grow}(\mathscr{T})grow(T) 是完备
2020-08-21 19:48:17
904
原创 【NOI2020 制作菜品】
题意有 nnn 种材料和 mmm 种菜品，每种菜品需要 kkk 克材料，且同一种菜品只能使用至多两种不同的材料。第 iii 种材料有 did_idi 克，满足 ∑di=m∗k\sum d_i = m*k∑di=m∗k。问是否存在一种合法的制作菜品方案？要求输出方案。n≤500,m,k≤5000n\le 500,m,k\le 5000n≤500,m,k≤5000分析刚看题的时候被数据范围误到，一直在往网络流和霍尔定理的方向思考。考虑 m=n−1m=n-1m=n−1 的部分分，发现最小且非零的 d
2020-08-21 10:09:36
428
原创 【NOI2020 命运】【线段树合并】
题意给一棵 nnn 个点的有根树和 mmm 条祖先-后代链，要求给每条边赋值 000 或 111，问有多少种方案满足每条链上至少有一条边的值为 111。n,m≤5∗105n,m\le 5*10^5n,m≤5∗105分析考虑容斥。强制让若干条链不满足，贡献就是链上的边只能取 000，其余边的值可以随便取的方案数，容斥系数为 (−1)k(-1)^k(−1)k，其中 kkk 为选择的链数量。树形dp。令 fi,jf_{i,j}fi,j 表示以 iii 为根的子树，从 iii 到深度为 jjj 的祖先路
2020-08-19 17:03:14
560
原创 【LibreOJ 154 集合划分计数】【集合幂级数+多项式k-exp】
题意有一个大小为 nnn 的集合 SSS 和 SSS 的子集族 F={S0,S1,⋯ ,Sm−1}{F}=\{S_0,S_1,\cdots,S_{m-1}\}F={S0,S1,⋯,Sm−1}。要求从 FFF 中选出不超过 kkk 个集合，使得这些集合的并为 SSS，且两两的交为空。问有多少种不同的选择方案。k≤n≤21,m≤262144k\le n\le 21,m\le 262144k≤n≤21,m≤262144分析设 fff 为 FFF 对应的集合幂级数，若定义乘法为子集卷积，那么要求的就是
2020-08-12 10:51:28
473
原创 【洛谷 P4548 [CTSC2006]歌唱王国】【概率生成函数+KMP】
题意给一个长度为 nnn 的序列 AAA。有一个空序列 BBB，每次会等概率随机往该序列的末尾加入 111 到 mmm 中的一个整数，若 AAA 成为了 BBB 的子串，则停止。求序列 BBB 的期望长度。n≤105n\le 10^5n≤105分析定义一个离散随机变量 XXX 的概率生成函数为F(z)=∑i≥0P(X=i)ziF(z)=\sum_{i\ge 0}P(X = i)z^iF(z)=i≥0∑P(X=i)zi其中 P(X=i)P(X=i)P(X=i) 表示 XXX 取值为 iii 的概率
2020-07-31 09:33:39
334
原创 Lyndon分解学习小记
Lyndon分解Lyndon串如果一个串的字典序不大于它的所有后缀，这样的串就称为 Lyndon 串。Lyndon分解将字符串 sss 分解为 w1w2⋯wkw_1w_2\cdots w_kw1w2⋯wk，若满足 w1,w2,⋯ ,wkw_1,w_2,\cdots,w_kw1,w2,⋯,wk都是 Lyndon 串，且 w1≥w2≥⋯≥wkw_1\ge w_2\ge \cdots \ge w_kw1≥w2≥⋯≥wk，则称 w1w2⋯wkw_1w_2\cdots w_kw1w2⋯w
2020-07-22 23:32:07
514
1
原创 【Codeforces 827F Dirty Arkady‘s Kitchen】【图论】
题意给一个 nnn 个点 mmm 条边的无向图，经过每条边的时间为 111，每条边有一个可以使用的时间区间 [li,ri][l_i,r_i][li,ri]。每个时刻必须移动到与当前点有边相连的一个点上。问从 111 到 nnn 花费的最小时间。n,m≤5∗105n,m\le 5*10^5n,m≤5∗105分析注意到可以在一条边上反复横跳，不妨把点按照奇偶性拆分成两个，边按照两个方向和奇偶性拆分成四条。维护 latex,0/1late_{x,0/1}latex,0/1 表示在奇/偶时刻到达 x
2020-07-17 10:26:03
289
原创 【51nod 1986 Jason曾不想做的数论题】【数论】
题意给定n,mn, mn,m，求∏X∈[1,m]nlcm(X1,⋯ ,Xn)gcd(X1,⋯ ,Xn)\prod_{X\in [1,m]^n}\mathrm{lcm}(X_1,\cdots,X_n)^{\gcd(X_1,\cdots,X_n)}X∈[1,m]n∏lcm(X1,⋯,Xn)gcd(X1,⋯,Xn)X∈[1,m]nX\in [1,m]^nX∈[1,m]n表示XXX取遍所有长度为nnn的序列，且XiX_iXi为111到mmm之间的整数。n≤109,m≤108n\le 10^9,m
2020-06-30 22:47:20
373
2
原创 【Codeforces 1148H Holy Diver】【可持久化线段树】
题意有nnn次操作和一个空序列，每次操作在序列末尾增加一个数，并询问区间[l,r][l,r][l,r]中有多少个子区间满足其mexmexmex等于kkk。强制在线。n≤200000n\le 200000n≤200000分析从小到大枚举右端点rrr，对于每个左端点lll，维护mex(al,⋯ ,ar)mex(a_l,\cdots,a_r)mex(al,⋯,ar)的值。mex(al,⋯ ,ar)mex(a_l,\cdots,a_r)mex(al,⋯,ar)的值对于lll而言肯定是单调不升的。新
2020-06-28 15:58:04
487
2
原创 【UOJ #269. 【清华集训2016】如何优雅地求和】【生成函数+下降幂多项式】
题意给出n,m,xn,m,xn,m,x和一个mmm次多项式f(x)f(x)f(x)在x=0,1,⋯ ,mx=0,1,\cdots,mx=0,1,⋯,m处的点值，计算∑k=0nf(k)(nk)xk(1−x)x−k\sum_{k=0}^nf(k)\binom{n}{k}x^k(1-x)^{x-k}k=0∑nf(k)(kn)xk(1−x)x−kn≤109,m≤2∗104n\le 10^9,m\le 2*10^4n≤109,m≤2∗104分析若我们已经把f(x)f(x)f(x)转成了下降幂多项式的形式f
2020-06-26 21:21:03
357
原创 【洛谷 P6151 [集训队作业2019] 青春猪头少年不会梦到兔女郎学姐】【容斥原理+生成函数】
题意定义一个序列的权值为：把序列首尾相接成一个环，环上每段数字长度的乘积。有nnn种数字，求所有满足第iii种数字恰好出现aia_iai次的排列的权值之和。n,∑ai≤2∗105n,\sum a_i\le 2*10^5n,∑ai≤2∗105分析先考虑序列上怎么做。设f(a,b)f(a,b)f(a,b)表示把aaa个无标号球分成bbb段的所有方案，每段长度乘积的和。可以理解成在每段中分别选一个数出来的方案，也就是在每两块隔板之间再放一块隔板，因此f(a,b)=(a+b−1b∗2−1)=(a+b−1
2020-06-26 10:50:42
447
原创 【Codechef POLYEVAL Evaluate the polynomial】【FFT】
题意nnn次多项式模ppp意义下多点求值。n≤250000,p=786433n\le 250000, p=786433n≤250000,p=786433分析可以直接上O(nlog2n)O(n\log^2n)O(nlog2n)的多项式多点求值（不可能的）。注意到，DFT的过程本身就是特殊的多点求值，对应的横坐标分别是ω0,ω,⋯ ,ωn−1\omega^0,\omega,\cdots,\omega^{n-1}ω0,ω,⋯,ωn−1，其中ω\omegaω是nnn次单位根。在NTT中，模ppp意义下n
2020-06-26 08:16:04
300
原创 【Codechef CLOWAY Future of draughts】【特征多项式+二项式反演】
题意给TTT张简单无向图。在每张图中选定一个标记点，每次选择若干个图（至少一个），把这些图中的点随机移向与其相连的一个点。若某个时刻当前状态与初始状态一致，就停止移动（也可以不停止）。每次询问给出l,r,kl,r,kl,r,k，问若对编号在[l,r][l,r][l,r]之间的图进行操作，有多少种可能的方案满足在kkk轮之前停止。T,ni≤50,k≤10000T,n_i\le 50,k\le 10000T,ni≤50,k≤10000分析可以先求出Gl,r,kG_{l, r, k}Gl,r,k表示对
2020-06-25 16:11:05
279
原创 【洛谷 P6624 [省选联考 2020 A 卷] 作业题】【矩阵树定理】
题意给一个nnn个点mmm条边的简单无向图，定义一棵生成树的权值为其边权和与边权gcd\gcdgcd的乘积。求所有生成树的权值和。n≤30,wi≤152501n\le 30,w_i\le 152501n≤30,wi≤152501分析将gcd\gcdgcd拆成欧拉函数求和的形式，得到ans=∑wφ(w)∗[所有边权都是w倍数的生成树权值和]ans=\sum_w\varphi(w)*[所有边权都是w倍数的生成树权值和]ans=w∑φ(w)∗[所有边权都是w倍数的生成树权值和]问题转化为如何求所
2020-06-24 23:09:17
325
1
原创 任意模数NTT学习小记
问题求两个多项式A(x)A(x)A(x)和B(x)B(x)B(x)对一个不是NTT模数的数取模的结果。拆系数FFT设置一个阈值WWW（通常设置为2152^{15}215），将A(x),B(x)A(x),B(x)A(x),B(x)拆分成A=aW+b,B=cW+dA=aW+b,B=cW+dA=aW+b,B=cW+d，其中a,b,c,da,b,c,da,b,c,d均为多项式。则AB=acW2+(ad+bc)W+bdAB=acW^2+(ad+bc)W+bdAB=acW2+(ad+bc)W+bd需要做777次
2020-06-24 18:30:08
241
原创 【Codechef DEVLOCK Devu and Locks】【倍增二维FFT】
题意求有多少个nnn位十进制数（可以有前导零），满足模ppp等于000且每一位数字之和不超过mmm。n≤109,p≤16,m≤15000n\le 10^9,p\le 16, m\le 15000n≤109,p≤16,m≤15000分析注意到第iii位贡献的系数为10i mod p10^i\bmod p10imodp，两位的贡献不同当且仅当对应系数不同。因此可以把数位按照系数分类。设numinum_inumi表示有多少位满足贡献系数为iii。numinum_inumi可以通过求10k10^k10k
2020-06-24 12:27:56
234
原创 【UOJ #424. 【集训队作业2018】count】【笛卡尔树+容斥原理】
题意设fA(l,r)f_A(l,r)fA(l,r)表示序列AAA中，A[l..r]A[l..r]A[l..r]中最大值的位置。若存在若干个最大值，则取最靠前的那一个。定义两个序列A,BA,BA,B同构，当且仅当两个序列长度相等，且对于任意l≤rl\le rl≤r都有fA(l,r)=fB(l,r)f_A(l,r)=f_B(l,r)fA(l,r)=fB(l,r)。问有多少个长度为nnn且不同构的序列，其中的元素为111到mmm中的整数，且每个整数在其中至少出现一次。n,m≤105n,m\le 10^5
2020-06-23 22:49:18
401
原创 【洛谷 P6623 [省选联考 2020 A 卷] 树】【Trie】
题意给一棵有根树，每个点有点权vxv_xvx。设xxx子树中的点为c1,⋯ ,ckc_1,\cdots,c_kc1,⋯,ck，定义fx=(vc1+dx,c1)⊕⋯⊕(vck+dx,ck)f_x=(v_{c_1}+d_{x,c_1})\oplus \cdots \oplus (v_{c_k}+d_{x, c_k})fx=(vc1+dx,c1)⊕⋯⊕(vck+dx,ck)其中dx,cid_{x, c_i}dx,ci表示xxx到cic_ici的距离。求f1+⋯+fnf_1+\cd
2020-06-23 17:03:51
271
原创 【洛谷 P6620 [2020 年联考 A 卷] 组合数问题】【组合数学】
题意计算(∑k=0nf(k)xk(nk)) mod p(\sum_{k=0}^nf(k)x^k\binom{n}{k})\bmod p(k=0∑nf(k)xk(kn))modp其中f(k)f(k)f(k)是一个mmm次多项式a0+a1k+⋯+amkma_0+a_1k+\cdots+a_mk^ma0+a1k+⋯+amkm。n,x,p,ai≤109,m≤1000n,x,p,a_i\le 10^9, m\le 1000n,x,p,ai≤109,m≤1000分析注意到mmm很小，考虑把mmm放
2020-06-23 12:40:44
247
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人