Makise Von's Blog

Tsukkomi

A 忘开 long long WA 一发，数组开小了 TLE 一发 qwq
B 又忘开 long long 又 WA 一发 他忘开 long long 一直可以的 qwq
C, D 直接不会，总得来说这场打得很僵硬 orz

Description

设

$f\left(n,k\right)=\sum_{a_1=2}^n\sum_{a_2=2}^n\dots\sum_{a_k=2}^n\left[\prod_{i=1}^ka_i=n\right]$

给定 $n,k$ $\left(1\leq n\leq2^{30},\ 1\leq k\leq30\right)$ ，求

$ans=\left(\sum\limits_{i=1}^nf\left(i,k\right)\right)\bmod\left(10^9+7\right)$

HDU 上为多组测试。

Tsukkomi

这场补完感觉挺有意思，比上一场 Div.2 稍难 qwq

Tsukkomi

好久没上 Codeforces ，家里的网络平时连镜像都上不去 orz
今天试了一下居然又能打开了，随便找了一场 Div.2 玩玩 qwq

Description

给定长度为 $n$ $\left(1\leq n\leq7.1\times10^3\right)$ 的序列 $a$ $\left(1\leq a_i\leq10^9\right)$ .
有一未知整数 $x\in\left[1,n\right]$ ，判断 $x$ 是否大于 $i$ 的代价为 $a_i$ .
现保证序列 $a$ 单调不降，求能确保求出 $x$ 所需的最小代价。
共 $T$ $\left(1\leq T\leq5\times10^2\right)$ 组测试，保证 $\sum n\leq7.1\times10^3$ .

Description

给定长度为 $2^n$ $\left(1\leq n\leq16\right)$ 的序列 $a$ $\left(0\leq a_i\leq2^{32}-1\right)$ ，下标从 $0$ 开始。
给定 $q$ $\left(1\leq q\leq2\times10^5\right)$ 次操作，操作分两种：

• $\left(1,l,r,k\right)$ $\left(0\leq l,r\leq2^n-1,\ 0\leq k\leq2^{32}-1\right)$ .
  表示对所有 $i\in\left[0,2^n\right),\ l\&i=l,\ i\&r=i$ ，令 $a_i=a_i+k$ .

• $\left(2,l,r\right)$ $\left(0\leq l,r\leq2^n-1\right)$ ，表示求

  $ans_{l,r}=\left(\sum_{l\&i=l,\ i\&r=i}a_i\right)\bmod2^{32}$

Excerpt from

今村昌弘
《尸人庄谜案》

Tutorial

阅读本文前应熟悉容量网络求 最大流 的 增广路算法 。
具体可参考 Maximum Flow Minimum Cut 的相关内容。

Minimum Cost Maximum Flow ，即 最小费用最大流 ，又称 费用流 。
它指的是 带费用的 容量网络上 总花费最小 的最大流。
下面将给出前置知识并介绍求费用流的算法，附板子题。

Tutorial

阅读本文前应熟悉 网络流基础 ，具体可参考 Network Flow .

Maximum Flow Minimum Cut ，即 最大流最小割 。
容量网络的 最大流 和 最小割 是网络流问题中常见的研究对象。
两者的关系由 Max-Flow Min-Cut Theorem ，即 最大流最小割定理 指出。
求最大流的算法包括 EK , Dinic , ISAP 和 HLPP 等。
下面将给出前置知识并分别介绍上述的 Theorem 和算法，附板子题。

Tutorial

Network Flow ，即 网络流 ，是 图论 中的一个重要分支。
下面将简述 网络流基础 ，参考 Wikipedia ：网络流