Night2002-CSDN博客

原创关于一类积性函数求和的优化——杜教筛

我是目录前置技能点有关积性函数的一些定义常见的一些积性函数前置技能点这是一些前置技能点，扫一眼目录，如果你都会就跳过吧。有关积性函数的一些定义如果一个函数 f(x)f(x)f(x) 的定义域为正整数域 Z+\mathbb{Z}^+Z+，值域为复数域 C\mathbb{C}C（即 f:Z+→Cf:\mathbb{Z}^+ \rightarrow \mathbb{C}f:Z+→C），那么称 ...

2018-12-13 21:55:25 578

原创 Night的数学杂谈——模数不互质的CRT

前置技能点要求懂得基础的数论知识和扩展欧几里德算法有关于前置技能点的东西不会就别问我了。写挂哪里请评论戳我。进入正题我们要合并同余方程 {x≡r1(modm1)x≡r2(modm2){x≡r1(modm1)x≡r2(modm2)\begin{cases}x\equiv r_1\pmod{m_1} \\ x\equiv r_2\pmod{m_2}\end{cases} 即： {...

2018-08-22 16:36:12 346

原创 [bzoj3622]已经没有什么好害怕的了动态规划

题意给定两个长度为 nnn 的序列 x,yx,yx,y，保证这两个序列没有相同的元素，求有多少匹配满足 xi>yixi>yix_i > y_i 的 iii 个数的比满足 xi<yixi<yix_iiii 的个数多 kkk 。数据范围对于 30%30%30\% 的测试数据，n≤15n≤15 n \le 15 对于 70%70%70\% 的测试数据，n≤20...

2018-05-28 17:02:13 258

原创 LOJ #508. 「LibreOJ NOI Round #1」失控的未来交通工具数论并查集

题目简述一个带边权无向图，有两种操作：加边以及询问在 x,x+b,...,x+(c−1)bx,x+b,...,x+(c−1)bx,x+b,...,x+(c−1)b 这些数中，有多少存在一条与之模 mmm 同余的从 uuu 到 vvv 的路径（可以不是简单路径）。数据范围 Subtask # 分值 ...

2018-05-19 17:40:43 626

原创「九省联考 2018」IIIDX 贪心线段树

【题目背景】Osu 听过没？那是 Konano 最喜欢的一款音乐游戏，而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在，他在世界知名游戏公司 KONMAI 内工作，离他的梦想也越来越近了。这款音乐游戏内一般都包含了许多歌曲，歌曲越多，玩家越不易玩腻。同时，为了使玩家在游戏上氪更多的金钱花更多的时间，游戏一开始一般都不会将所有曲目公开，有些曲目你需要通关某首特定歌曲才会解锁，而且越晚...

2018-04-30 21:34:25 469

原创 [FJWC2017]区间

【问题描述】AAA 君有一个长度为 nnn 的排列 PPP, 现在 AAA 君想知道，有多少个连续整数组成的区间 [l,r][l,r][l, r] 可以由 PPP 中的两个区间 [a,b],[c,d][a,b],[c,d][a, b], [c, d] 拼出，其中 1≤a≤b<c≤d≤n1≤a≤b<c≤d≤n1 \le a \le b < c \le d \le n。例如 P=[...

2018-04-26 17:39:33 265

原创 [FJWC2017]生日礼物-TopCoder Member SRM 494 Div 1 KnightsOut

给出一个N*M的方格棋盘，每个格子里有一盏灯和一个开关，开始的时候，所有的灯都是关着的。用(x, y)表示第x行，y列的格子。(x, y)的开关可以改变(x, y)中灯的状态，同时也可以改变满足|x’-x|=2,|y’-y|=1或者|x’-x|=1,|y’-y|=2的格子(x’, y’)的状态。改变状态的意思是，原来开着的灯会被关掉，原来关着的灯会被开起来。注意这边的改变状态是强制改变的。每个格子的开关最多只能按一次

2018-04-26 17:30:55 475

原创 Night关于数学的杂谈-插值法

插值法是什么插值，就是给定一定的离散数据点，范围内估计新数据点的过程或方法。在这个过程中，我们当然希望得到一个连续的光滑曲线同时经过所有的 (xi,yi)(xi,yi)(x_i,y_i) ，并求得该曲线在需要求值的点上的值。具体定义如下：给定 nnn 个离散数据点 (xi,yi)&amp;amp;amp;amp;nbsp;(i∈[1,n])(xi,yi)&amp;amp;amp;amp;nbsp;(i∈[1,n])(x_i,y_i) \ (i \i...

2018-04-17 09:44:55 510

原创 Night的算法杂谈-2SAT问题

SAT问题总述SAT是适定性(Satisfiability)问题的简称。一般形式称为k-适定性问题，简称 k-SAT。形式化地描述如下：设 A={a1,a2,⋯,an}A={a1,a2,⋯,an}A = \{ a_1,a_2, \cdots ,a_n\} 为一个有限个布尔变量所构成的集合，A^={a1,a2,⋯,an,¬a1,¬a2,⋯,¬an}A^={a1,a2,⋯,an,¬a1,¬...

2018-03-29 20:18:51 532 1

原创 Night的数据结构杂谈-可持久化线段树

要想知道可持久化线段树是什么呢，我们得先了解一下所谓“可持久化”这四个字代表什么。恩一个可持久化数据结构（persistent data structure）就是一个可以在操作时保留自身先前版本的数据结构。那么怎么支持可持久化呢？最简单的方案当然就是每次操作我们重新建立一个数据结构，然后将之前的操作全部都在这个结构上进行一次，然后接着进行当前操作。或者是可以对于第 iii 次操作，我们把第...

2018-03-22 19:16:58 282

原创 Night的数据结构杂谈-虚树

在某些时候，我们需要维护树上选一些点所得到的东西。这些东西要满足这样一个性质：未选的点可以通过某种方式删除而不影响最终的结果。最典型的就是求被选出的节点在原树上的距离之和。既然我们知道未选的点可以删掉，那么我们就想办法建一棵树，使得树上的未选点尽量少。这棵树就叫虚树。那么要怎么建立一棵虚树呢？首先我们在原树上跑一遍 dfsdfsdfs，并得出树上节点的 dfsdfsdfs ...

2018-03-17 14:53:08 776 1

原创记2018.2.27 NOIP班-数据结构(9)

t1: 题意简述：给你 nnn 个线性函数 fi=kix+bifi=kix+bif_i=k_i x+b_i，支持单点修改和区间查询 fr(fr−1(⋯fl(x)⋯))mod (109+7)fr(fr−1(⋯fl(x)⋯))mod (109+7)f_r(f_{r-1}(\cdots f_l(x)\cdots )) \bmod\ (10^9+7)。然后看了题目...

2018-02-28 12:06:31 306 1

Night2002的博客