当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

分类 口胡 下的文章

你现在要洗 l 件衣服。你有 n 台洗衣机和 m 台烘干机。由于你的机器非常的小,因此你每次只能洗涤(烘干)一件衣服。

i 台洗衣机洗一件衣服需要 w_i 分钟,第 i 台烘干机烘干一件衣服需要 d_i 分钟。

请问把所有衣服洗干净并烘干,最少需要多少时间?假设衣服在机器间转移不需要时间,并且洗完的衣服可以过一会再烘干。

l \leq 10 ^ 6, n, m \leq 10 ^ 5

READ MORE

一枚棋子要从 (0,0) 跳到 (T_x,T_y)。每一步只能向右上方跳,且横坐标变化不能超过 M_x,纵坐标变化不能超过 M_y,每一次跳跃不能停留在原地。

K 个向量是非法的,这些向量形如 (k_i,k_i) ,会在读入中给出。也就是说,每一步 x,y 的增量不能同时等于 k_i所有的 k_i 都是 G 的倍数。

求从 (0,0),跳恰好 R 步到 (T_x,T_y) 的方案数。答案对 10^9+7 取模。

T,M \leq 10^6,\ R \leq 1000,\ 10000 \leq G \leq 50000,\ K \leq 50

READ MORE

假设 f_i 表示第 i 步恰好结束的概率,g_i 表示第 i 步还未结束的概率,h_{k, i} 表示第 i 步恰好结束并且以字符 k 结尾的概率。F(x), G(x), H(x) 分别是 \{f_i\}_{i=0}^\infty, \{g_i\}_{i=0}^\infty, \{h_i\}_{i=0}^\infty 的普通生成函数。

显然我们知道 F(1) = 1 ,要求 E = F'(1)

READ MORE

对于给定的 n+1 个点的坐标可以列出 n+1 个方程

\begin{cases} \left( a_{1, 1} - x_1 \right)^2 + \left( a_{1, 2} - x_2 \right)^2 + ... + \left( a_{1, n} - x_n \right)^2 = r^2 \\ \left( a_{2, 1} - x_1 \right)^2 + \left( a_{2, 2} - x_2 \right)^2 + ... + \left( a_{2, n} - x_n \right)^2 = r^2 \\ ... \\ \left( a_{n+1, 1} - x_1 \right)^2 + \left( a_{n+1, 2} - x_2 \right)^2 + ... + \left( a_{n+1, n} - x_n \right)^2 = r^2 \\ \end{cases}

考虑展开以后的 r^2x_{1...n}^2 比较难以处理。让 [2, n + 1] 方程与第一个方程做差,得到 n 个线性方程

\begin{cases} a_{2, 1}^2 - a_{1, 1}^2 - 2 x_1 (a_{2, 1} - a_{1, 1}) + a_{2, 2}^2 - a_{1, 2}^2 - 2 x_1 (a_{2, 2} - a_{1, 2}) + ... + a_{2, n}^2 - a_{1, n}^2 - 2 x_1 (a_{2, n} - a_{1, n}) = 0 \\ a_{3, 1}^2 - a_{1, 1}^2 - 2 x_1 (a_{3, 1} - a_{1, 1}) + a_{3, 2}^2 - a_{1, 2}^2 - 2 x_1 (a_{3, 2} - a_{1, 2}) + ... + a_{3, n}^2 - a_{1, n}^2 - 2 x_1 (a_{3, n} - a_{1, n}) = 0 \\ ...\\ a_{n+1, 1}^2 - a_{1, 1}^2 - 2 x_1 (a_{n+1, 1} - a_{1, 1}) + a_{n+1, 2}^2 - a_{1, 2}^2 - 2 x_1 (a_{n+1, 2} - a_{1, 2}) + ... + a_{n+1, n}^2 - a_{1, n}^2 - 2 x_1 (a_{n+1, n} - a_{1, n}) = 0 \\ \end{cases}

高斯消元即可求得

可以发现每条边出现的概率都是相同的,那么

ans = \frac{2 n^{n-3}}{n^{n-2}} \sum_{i=1}^{n} \sum_{j=i+1}^{n} (i+j)^k = \frac 2 n \sum_{i=1}^n \sum_{j=i+1}^n (i+j)^k

只需要求后面的值,假设 f(n, k) = \sum_{i=1}^n i^k

\begin{aligned} \sum_{i=1}^n \sum_{j=i+1}^n (i+j)^k &= \frac 1 2 \left( \sum_{i=1}^n \sum_{j=1}^n (i+j)^k - \sum_{i=1}^n (i+i)^k \right) \\ &= 2^{-1} \sum_{i=1}^n \sum_{j=1}^n (i+j)^k - 2^{k-1} \sum_{i=1}^n i^k \\ &= 2^{-1} \sum_{i=1}^n \sum_{j=1}^n (i+j)^k - 2^{k-1} f(n, k) \end{aligned}

只需要求中间的那个双重和式,后面的可以插值

\begin{aligned} \sum_{i=1}^n \sum_{j=1}^n (i+j)^k &= \sum_{d=1}^{2n} d^k \sum_{i=1}^n \sum_{j=1}^n [i+j=d] \\ &= \sum_{d=1}^n d^k (d-1) + \sum_{d=n}^{2n} d^k \left(2n-(d-1)\right) \\ &= \sum_{d=1}^{n-1} d^{k+1} + \sum_{d=n}^{2n} 2n d^k - \sum_{d=n-1}^{2n-1} d^{k+1} \\ &= f(n-1, k+1) + 2n \left( f(2n, k) - f(n-1, k) \right) - \left( f(2n-1, k+1) - f(n-2, k+1)\right)\\ \end{aligned}

可以处理出 f(n, k), f(2n, k), f(n, k+1), f(2n, k+1) 并快速转移。复杂度为拉格朗日插值的复杂度。

发现主要瓶颈在于 1. 求快速幂 2. 求逆元 。前者是一个完全积性函数,可以使用线性筛求得;后者我们可以先线性求逆元,然后分别做一趟前缀 / 后缀和即可。

定义一个图是好图当且仅当:

  • 这个图只有一个点
  • 这个图可以被划分为若干个好图
  • 这个图的补图是好图

n 个点的的本质不同的好图数量,定义两个好图是本质相同的当且仅当可以通过重标号一个好图得到另外一个。

READ MORE

考虑答案的生成函数 f(x)ans = [x^s]f(x) ,设 d(x) = \sum\limits_{i=0}^{\infty} [i \in D] x^i

则显然 f(x) = d(f(x)) + x ,可以理解为我们硬点了一个点作为根,然后每棵子树都可以选择,而新得到的生成函数显然与原来的是等价的。

READ MORE