给定正整数N, 求1≤x,y≤N且Gcd(x,y)为素数的数对(x,y)的对数. (1≤N≤10^7)

Read More

这一场比较水, 然而掉了rating......E题是原题, 连我都知道是原题, 可见多么裸. 但是比赛时只完成2/5, C题FST, E题手抖......而且都是被sqrt这个函数坑了...... 但是我要为出题人点赞. 他的Editorial写得非常详细, 有Hint, 有Tutorial, 还有至少两种语言的实现, 诚意满满. D是道不错的数学题. UPDATE: 经过提醒才发现Editorial为E题给了一种不带log的做法, 后面将会叙述. 题解: 5/5.

Read More

阐述见快速傅立叶变换及其逆变换.

Read More

本文是对FFT及iFFT的简要介绍, 包括原理的证明和代码实现 (不包括应用). 基层的原理我也不清楚啦......比如复数次幂到底是怎么回事, 比如范德蒙德矩阵的行列式怎么算 (不会线代TAT), 但是这里给出的证明在假定这些事实的基础上是正确的.

个人认为本文的优点在于比较简洁, 最后给毛爷论文里提到的合并DFT的技巧给了个简单的证明.

参考文献: <算法导论>, 毛爷爷 <再探快速傅立叶变换>, Picks的博客, vfk <炫酷反演魔术>, uoj 34 上的优秀代码.

前置技能: 复数的加减乘法, 多项式的基本概念, 矩阵的基本概念.

Read More

长度为n的正整数序列, m条指令. 每条指令询问区间[l, r]中共有多少种不同的数, 或将第p个数修改为c. (n,m≤10^5, 修改操作不多于10^3次, 所有整数属于[1,10^6])

Read More

有一个可以在1单位时间内交换两个相邻数的排序程序. n个数的序列, q个询问, 问将[l,r]内的数排成升序最少需要交换多少次. (n,q≤5*10^4)

Read More

n个点的无根树, m种糖, 每个点有某种糖, 每种糖有权值d, 第i次吃某种糖有系数wi, 每次吃糖使愉悦指数增加权值x系数. q个操作, 每个操作修改某结点的糖的种类, 或者询问沿u到v的唯一路径一路吃过去的愉悦指数. (1≤di,wi≤10^6, wi是非递增序列, n,m,q≤10^5)

Read More

把一棵N个点的无根树分成一些块, 使得每块的大小属于[B, 3B], 并且每块存在一个点, 块内所有点到该点的路径上的点均在块内 (但是该点可以在块外). 构造一种方案 (输出块数, 每个点所属的块的编号, 每块对应的那个特殊点, 允许多对一), 或者报告无解. (1≤N≤1000, 1≤B≤N)

Read More

给一个长为n的自然数序列{a}和m个询问, 求区间mex (未出现的最小自然数). (1≤n,m≤2*10^5, 0≤ai≤10^9) 这是一道做法很多的题. 可以离线, 可以在线, 可以带根号, 也可以不带根号.

Read More

N个点M条边的无向图, K个询问, 问保留图中编号在[l,r]的边的时候图中的连通块个数. 强制在线. (1≤N,M,K≤200,000) 很妙的一道题.

Read More

维护一片点带权的森林. 森林最初是一棵N个点的树, 接着有M个操作: 删边, 连边, 路径加, 询问某路径上任取两点 (可相同) 路径上权值之和的期望 (输出一个既约分数). (1≤N≤5*10^4, 1≤M≤5*10^4, 前三种操作不合法则忽略, 询问的两点不连通则输出-1)

Read More

N个点M条边的简单无向图, Q个操作, 每个操作断掉一条边, 或询问两点间路径最大值的最小值. (N≤10^5, M≤10^6, Q≤10^5, 保证任意时刻图连通)

Read More

维护一棵n个点的树, 初始权值为1, 支持: 路径权值加, 删除一条边并加入一条边 (保证操作完是一棵树), 路径权值乘, 询问路径点权和模51061的结果. (1≤n,q≤10^5, 0≤c≤10^4) 其实c的范围并不是这个. 爆int被坑了几次, 这次专门对每个式子计算了一番, 然后放心地提交, WA掉. 看了几个题解, 发现大家用unsigned, AC. 人与人起码的信任哪里去了......TAT

Read More

维护一片森林, 支持Connect, Destroy和查询连通性. 点数n≤10000, 操作数m≤200000.

Read More

以下是题解. 6/6 比赛时只完成了前三道.

Read More