Rockdu's Blog

原来一直只把调和级数(Hn" role="presentation" style="position: relative;">HnHnH_n)当成算复杂度的工具。 直到遇到了这样一道题： T2062 随机数生成器 通过打表可以发现，答案就是Hn+1" role="presentation" style="position: relative;">Hn+1Hn+1H_n+1 但是n" role="presentation" style="position: relative;">nnn太大，调和数本身也没有通项公式。 在说这道题之前，我们先来说说调和数是什么吧

2.1 题目描述 九条可怜是一个热爱游戏的女孩子，她经常在网上和一些网友们玩一款叫做《僵尸危机》 游戏。 在这款游戏中，玩家们会需要在成为僵尸之前与黑恶势力斗智斗勇，逃离被病毒感染的小 岛。但是黑恶势力不会让玩家轻易得逞，他会把一些玩家抓走改造成僵尸。变成僵尸的玩家会 攻击其他的玩家，被攻击的玩家会被” 感染”，成为病毒的潜在宿主。 具体来说，游戏开始时，所有的玩家会获得一个 l ∼ r 的编号 (如果一共有 r − l + 1 个玩 家)，不同的玩家的编号不同。 游戏分轮次进行，在每一轮中一次会发生这样的事情。 • 如果所有当前所有的正常人都已经被感染，那么游戏结束。 •

题目背景 2018年11月17日，中国香港将会迎来一场XM大战，是世界各地的ENLIGHTENED与RESISTANCE开战的地点，某地 的ENLIGHTENED总部也想派Agent去参加这次的XM大战，与世界其他地方的ENLIGHTENED并肩作战。 题目描述 某地的ENLIGHTENED总部总部有N" role="presentation" style="position: relative;">NNN个Agent，每个Agent的能力值互不相同，现在ENLIGHTENED行动指挥想要派出A,B两队Agent去参加XM大战。但是参加大战的两个队伍要满足两个要求： A队中能

1.1 题目描述 九条可怜是一个热爱思考的女孩子。 九条可怜最近正在研究各种排序的性质，她发现了一种很有趣的排序方法：gobo sort！ Gobo sort 的算法描述大致如下： • 1. 假设我们要对一个大小为 n 的数列 a 排序。 • 2. 等概率随机生成一个大小为 n 的排列 p 。 • 3. 构造一个大小为 n 的数列 b 满足 bi = api，检查 b 是否有序，如果 b 已经有序了就结 束算法，并返回 b ，不然返回步骤 2 。 显然这个算法的期望时间复杂度是 O(n × n!) 的，但是九条可怜惊奇的发现，利用量子的 神奇性质，在量子系统中，可以把这个算法

题目描述 组合数 Cnm" role="presentation" style="position: relative;">CmnCnmC_n^m 表示的是从 n" role="presentation" style="position: relative;">nnn 个物品中选出 m" role="presentation" style="position: relative;">mmm 个物品的方案数。举个例子，从 (1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 Cnm" rol

http://uoj.ac/problem/396 一、一些小处理 首先，每一条龙该使用哪一把剑是严格确定的，这个可以用set加lower_bound预处理出来。我们发现，要想打死一条龙，需要满足的条件是： $$ atk_ix\equiv hp_i(mod\ p_i) 且 atk_ix \geq hp_i $$ 其中$atk_i$是预处理出的攻击力，$hp_i$是巨龙的血量，$p_i$是恢复能力。 对于后面的限制是好做的，只要求出前面同余方程组的解就可以解出满足后面性质的最小解。 对于前面形如$ax\equiv c(mod\ p) $的方程，我们用扩展欧几里得对$x$求解

Problem Description Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divi

Given a list of integers (A1, A2, ..., An), and a positive integer M, please find the number of positive integers that are not greater than M and dividable by any integer from the given list. Input   The input contains several test cases. For each test case, there are two lines. The first line

【题目描述】 求n个点的有向图的强连通图的个数对998244353取模后得结果(无重边，无自环) 定义强连通图为本身为强连通分量的图 【输入格式】 输入一个n表示点数 【输出格式】 输出题目要求的答案 【样例输入】 2 【样例输出】 1 【提示】 对于30%的数据，n<=1000 对于100%的数据，n<=100000 30分的做法详见：网上一篇很好的博客 这个东西是个卷积形式，很容易想到生成函数。 我们来回顾一下两个式子： f(n)=g(n)+∑k=0n(n−1k−1)f(k)g(n−k) f(n)=g(n)+\sum^{n}_

【题目描述】 求n个点的有向图中强连通图的个数，输出答案对10007取模后得结果(无重边，无自环) 定义强连通图为本身是一个强连通分量的图 【输入格式】 输入一个n表示节点个数 【输出格式】 输出题目要求的答案 【样例输入】 【样例输出】 【提示】 样例解释： 只有一个图，即有边<1,2>和边<2,1> 对于30%的数据，n<=7 对于100%的数据，n<=1000 几个月之前想过强连通图的计数问题，发现根本不可做，暑假集训突然就变成作业了…… 这道题的容斥姿势太高超了，功力不够学不来QWQ。 考虑模仿