BZOJ3143 「HNOI2013」游走

Description

$n$ 个点 $m$ 条边的无向连通图,在上面从 $1$ 号点开始随机游走。现在你可以给每条边从 $1$ 到 $m$ 编号作为分数(经过就得分)。求如何编号使得总分的期望最小。输出这个最小值即可。

$n \leq 500$

Description

有 $n$ 张卡牌,$r$ 局游戏,每张卡牌有 $p_i$ 的概率发动技能,如果发动会造成 $d_i​$ 的伤害。每局游戏从第一张卡牌开始开始一个个遍历,如果发动过技能则忽略继续;否则如果这张卡牌现在发动了,则结束回合;没有发动则继续。求造成的总伤害的期望。

BZOJ2134 单选错位

Description

$n$ 道题,第 $i$ 道题有 $a_i$ 个选项。求将正确答案全部右移一位(第 $n$ 题移到第 $1$ 题)之后期望对的题数

BZOJ4665 小w的喜糖

Description

$n$ 颗糖发给了 $n$ 个人,每颗糖有一个种类。$n$ 个人相互交换手中的糖那么有多少种方案使得每个人手中的糖的种类都与原来不同。

两个方案不同当且仅当,存在一个人,他手中的糖的种类在两个方案中不一样。

答案对 $10^9 + 9$ 取模

BZOJ4361 isn

Description

给出一个长度为 $n$ 的序列 $A(A_1,A_2 \cdot A_n)$。如果序列 $A$ 不是非降的,你必须从中删去一个数这一操作,直到 $A$ 非降为止。求有多少种不同的操作方案,答案模 $10^9+7$ 。

BZOJ2839 集合计数

Description

从大小为 $n$ 的集合中取出若干子集(至少一个),使得它们的交集的元素个数为 $K$ ,求取法的方案数,答案模$1000000007$

Description

一共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$ 。某人去商店买东西,去了 $tot$ 次。每次带 $d_i$ 枚 $c_i$ 硬币,买 $s$ 的价值的东西。请问每次有多少种付款方法。

类欧几里得算法用来求诸如此类问题:

杜教筛学习笔记

设现在要求积性函数 $f$ 的前缀和, 设 $\sum \limits_{i=1}^{n} f(i) = S(n)$。

再找一个积性函数 $g$ ,则考虑它们的狄利克雷卷积的前缀和

其中得到第一行是根据狄利克雷卷积的定义。

得到第二行则是先枚举 $d$ 提出 $g$ 。

得到第三行则是把 $\sum\limits _{i=1}^{\lfloor \frac{n}{d}\rfloor } f(i) $ 替换为 $S(\lfloor \frac{n}{d} \rfloor) $

接着考虑 $g(1)S(n)$ 等于什么。

可以发现,他就等于

(可以理解成从1开始的前缀和减去从2开始的前缀和就是第一项)

前面这个式子 $\sum \limits _{i=1}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor)$

根据刚才的推导,他就等于 $\sum\limits_{i=1}^{n}(f*g)(i)$

所以得到杜教筛的核心式子:

得到这个式子之后有什么用呢?

现在如果可以找到一个合适的积性函数 $g$ ,使得可以快速算出 $\sum\limits_{i=1}^{n}(f*g)(i)$ 和 $g$ 的前缀和,便可以用数论分块递归地求解。

代码按照理解大概可以写成这样(默认 lllong long
(可以理解成一个伪代码。。就是一个思路的框架)

1
2
3
4
5
6
7
8
9
10
ll GetSum(int n) { // 算 f 前缀和的函数
ll ans = f_g_sum(n); // 算 f * g 的前缀和
// 以下这个 for 循环是数论分块
for(ll l = 2, r; l <= n; l = r + 1) { // 注意从 2 开始
r = (n / (n / l));
ans -= (g_sum(r) - g_sum(l - 1)) * GetSum(n / l);
// g_sum 是 g 的前缀和
// 递归 GetSum 求解
} return ans;
}

这个代码的复杂度是 $O(n^{\frac{3}{4}})$,证明如下:

设求出 $S(n)$ 的复杂度是 $T(n)$ ,要求出 $S(n)$ 需要求出 $\sqrt n$ 个 $S (\lfloor \frac{n}{i} \rfloor)$ 的值,结合数论分块的复杂度 $O(\sqrt n)$ 可得:

还可以进一步优化杜教筛,即先线性筛出前 $m$ 个答案,之后再用杜教筛。这个优化之后的复杂度是:

当 $m = n ^ {\frac{2}{3}}$ 时,$T(n) = O(n^{\frac{2}{3}})$

可以使用哈希表来存下已经求过的答案,也可以不用。

考虑到上面的求和过程中出现的都是 $\lfloor \frac{n}{i} \rfloor $ 。开一个大小为两倍 $\sqrt n$ 的数组 $dp$ 记录答案。如果现在需要求出 GetSum(x) ,若 $x \leq \sqrt n$ ,返回 dp[x] ,否则返回 dp[sqrt n + n / i] 即可。这样可以省去哈希表的复杂度。

BZOJ3160 万径人踪灭

Description

给定一个字符串由 ‘a’ 或 ‘b’ 组成。求有多少个子序列满足字母和坐标都关于一条对称轴对称并且不是连续的

字符串长度 $=n \leq 10^5$

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×