TsinsenA1221 大楼

题目链接

题意

给出一张带权图, 从 $1$ 结点出发, 问最少走过多少条边, 使得权值总和大于等于 $m$ 。
$1\leq n\leq 100, 1\leq m\leq 10^{18} $

题解

发现给出了一个邻接矩阵,而且从 $i\to k$ 和从 $k\to j$ 的权值和可以更新 $i\to j$ 的最大权值和
可以看做用邻接矩阵中 $g[i][k]+g[k][j]$ 来更新 $g[i][j]$
于是类似于矩乘的做矩阵快速幂棵快速得到走过 $l$ 条边的最大权值
继续阅读

单位根反演备忘录

之前 Picks 来讲课,结果 Guideposts 那题被 boshi 秒了 boshi讲完我还在下面懵逼
后来去学了单位根反演

单位根反演

具体来说,就是将 $[n\mid k]$ 转化为一个容易化简,求值,带入的式子
$$ [n\mid k] = \frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ki} $$

证明

  1. 当 $n\mid k$ 时,设 $k=t\cdot n$ ,则
    $$ \frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ki} = \frac{\sum_{i=0}^{n-1}\omega_n^{n\cdot(ti)}}{n} =1=[n\mid k]$$
    继续阅读

BZOJ4911 切树游戏

建议在 LOJ 上提交

题解

一开始想用点分治然后DP,结果发现会统计不合法答案,后来去看题解了,发现这题简直神题
算法:动态dp+FWT
虽然题目中表示树是无根的,但是我们还是可以随便选一个点作为根
设 $f(i,k)$ 为以 $i$ 为根节点的子树,异或值为 $k$ 的联通子树个数
发现某个节点的 $f$ 值可以从所有子树的 $f$ 做异或卷积转移得来
具体地说,设 $F_i(z)$ 代表 $i$ 的 $f$ 数组的生成函数,则
$$ F_i(z) = z^{v_i} \prod (F_{son_i}(z)+z^0)$$
其中卷积为异或卷积
继续阅读

BZOJ5153 州区划分

bzoj上不能测试这题,需要下载数据手动测试,我写了个linux上的简易测试脚本
下载本地测试文件,将自己的程序重命名为 5153.cpp 放进解压后的文件夹里,然后把从 bzoj 上下载的数据也放进去,输入 sh test.sh 等待结果就行
update: 后来发现 UOJ 上也有

题面

链接

题解

设 $f _ S$ 为点集为 $S$ 时的答案,$g _ S$ 为点集为 $S$ 且点集对应的图合法时集合中所有点的权值和,$sum _ S$ 为点集 $S$ 中所有点的权值和
显然,当 $S$ 合法时 $g _ S=sum _ S$ ,否则 $g _ S=0$
根据题目
$$ f _ S=\sum _ {T\subseteq S} f _ {S-T}\times \big{(}\frac{g _ T}{sum _ S}\big{)}^p $$
继续阅读

BZOJ4036 按位或

vfk 论文上的一道例题

题意

给出 $n$ ,每秒会有 $p_i$ 的概率选择 $i ,i \in [0, 2^n – 1]$ ,与手上的数进行异或,问期望多少次后手上的数会变成 $2^n-1$

题解

果然还是应该用 $\hat f$ 来表示 $f$ 的莫比乌斯变换,不然我整个人都比较懵
设 $f_i$ 表示操作 $i$ 次后得到数字的概率的生成函数, $U$ 为 $2^n – 1$
设 $h_S$ 表示得到 $S$ 的期望操作次数,将 $f$ 看成集合幂级数,则
$$ h_S = \sum_{k=1}^{\infty} k\cdot(f^k – f^{k-1}) $$
继续阅读

BZOJ3695 滑行

题意

一个矩形的地面被划分成不同的 $N$ 块,每块的高度为 $H[i]$ ,每块的长度都为 $X$ ,现在有一个滑块,给出在每个块上的限速$V[i]$ ,求从右上角到左下角最短时间是多少

题解

这题在 miskcoo的博客上看到的,感觉挺神奇的
用到两个物理定理来解决这题
1. 光的最速原理:光从一点射到另一点,用的路径一定是所有路径中最短的
2. 折射定律:光的入射角 $\theta_1$ 和折射角 $\theta_2$ 与光在两块介质中的速度 $v_1$, $v_2$ 有如下关系:
$$ \frac{\sin \theta_1}{v_1}=\frac{\sin\theta_2}{v_2} $$
继续阅读

BZOJ3684 大朋友和多叉树

题目链接

题解

这题做的我心累
一开始怎么想都不知道这个怎么用生成函数搞
后来去看题解。。。好吧是我太菜了
设 $F(x)$ 为方案数的 $OGF$
于是有转移
$$ F(x)=x + \sum_{i\in D} F^i(x)$$
解释一下,前面的 $x$ 是指叶子节点,也就是权值为 $1$ 时的方案数(显然只有一种),后面代表枚举儿子个数,用乘法原理将每个儿子的选择方案合起来,然后用加法原理把不同儿子数之间的方案合起来
继续阅读

BZOJ2259 新型计算机

本来按 lc 的多项式课件上写的 2259 来的,结果好像他把 cogs 上的题写成 BZOJ 了还是什么?
好吧反正这题和多项式没关系, cogs 也上不了我也没办法

题意

从前往后先读取第一个数字 S1,然后顺序向后读入 S1 个数字。接着再读一个数字 S2,顺序向后读入 S2 个数字…… 依此类推。只有所有的数恰好读完的序列才是合法的。
给出一个输入序列,可以对于序列中的任意一个数进行修改,使修改后的序列是合法序列。求操作的最小代价。设某个位置但是数是 x,把他变成 y 的代价是 abs (x-y)

题解

一开始怎么看样例都不对,感觉要 2 才行
最后才发现把第一个改成 3 就行了,估计没有比我更傻的了
继续阅读

BZOJ4555 求和

题意

设第二类斯特林数为 $S(n,k)$ 表示将 $n$ 个元素分为 $k$ 个无差异集合的方案数

$$ f(n)=\sum_{i=0}^{n}\sum_{j=0}^{i}S(i,j)\times 2^j \times (j!) $$

题解

发现当 $j>i$ 时后面的贡献为 $0$ 所以后面 $j$ 的范围可以枚举到 $n$ ,即
$$ f(n)=\sum_{i=0}^{n}\sum_{j=0}^{n}S(i,j)\times 2^j \times (j!) $$
首先推一下第二类斯特林数
$$ S(n,k)=\frac{1}{k!}\sum_{i=0}^{k}(-1)^i C_k^i (k-i)^n $$
继续阅读