Tellegens Principle

问题 给出一个 $m\times n$ 的矩阵 $A$,以及一个用于计算 $u\mapsto Au$ 的(线性的)算法,求一个几乎同样次数乘、同样次加减法的用于计算 $v\mapsto A^Tv$ 的算法。 本篇 Blog 是个人口嗨。 ...

一种多项式多点求值算法

Problem 给定一个 $m-1$ 次多项式 $f(x)$ 以及 $n$ 个点 $\alpha_0,\dots,\alpha_{n-1}$,求 $f(\alpha_0),f(\alpha_1),\dots,f(\alpha_{n-1})$。 参考:《转置原理的简单介绍》rushcheyo, negiizhao, Created_Equal 参考:EI’s blog 参考:Tellegen’s Principle into Practice ...

BZOJ4734 [清华集训2016] 如何优雅地求和

Description 已知 $m$ 次多项式函数 $f$ 在 $0,1\dots,m$ 处的取值 $f(0),f(1),\dots,f(m)$,给定 $n,x$,求 $$\left(\sum_{k=0}^n\binom nkf(k)x^k(1-x)^{n-k}\right)\bmod998244353$$ $n\leqslant10^9,m\leqslant2\times10^4$。 ...

LOJ565 [LR10] mathematican 的二进制

Description 一个初始为 0 的二进制数,有 $m$ 次操作。 第 $i$ 次操作是将这个二进制数加上 $2^{a_i}$ 。这个操作以 $p_i$ 的概率执行。 如果某次操作执行了并且修改了二进制数的 $k$ 位,那么它会带来 $k$ 的代价。 问代价和的期望,答案对 $998244353$ 取模。 $n=\max a_i\leqslant10^5, m\leqslant2\times10^5$ ...

LOJ6391 [THUPC2018] Tommy神的树

Description 一棵 $n$ 个结点的树。初始时 $a$ 和 $b$ 是黑的,其他点是白的。 每次可以把某个黑点染成红的并把与它相邻的白点染成黑的。 问把结点染红的顺序有多少种。 $1\leqslant a,b\leqslant n\leqslant234567$ 答案对 $998244353$ 取模,时限 10s 。 ...

CF947E Perpetual Subtraction

Description 有一个非负整数 $x$ 。你要执行 $m$ 次操作,每次操作是 x = randint(0, x) ( = 表示赋值, randint(0, x) 均匀随机地在 $[0, x]$ 中取一个整数)。 现在已知初始的 $x$ 会随机在 $[0, n]$ 取值,且取 $i$ 的概率是 $p_i$ ,求最后取到 $[0, n]$ 每个数的概率。 $$n\leqslant10^5, m\leqslant10^{18}$$ ...

BZOJ5119 [清华集训2017] 生成树计数

Description 一个$s$个点的图,目前被$s-n$条边连成了$n$个连通块,第$i$个连通块大小为$a_i$。要求你再连$n-1$条边把它变成一棵树。对于每一棵树,若第$i$个连通块连出了$d_i$条边,其价值为 $val(T)=\left(\prod_{i=1}^nd_i^m\right)\left(\sum_{i=1}^nd_i^m\right)$ 求所有生成树的价值和$\bmod998244353$。$n \leqslant 30000, m \leqslant 30$。 ...