警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

题意

传送门:AGC031 E - Snuke the Phantom Thief

给你一个 \(n\) 个点的点集 \(S\),和 \(m\) 条限制,第 \(i\) 个点 \((x_i,y_i)\) 有一个权值 \(v_i\)。你要选出一个集合 \(T\subseteq S\),最大化 \(\sum_{i\in T}i_v\),且满足所有的限制。限制有四种:

  • L a b\(\sum_{i\in T}[x_i\le a]\le b\)
  • R a b\(\sum_{i\in T}[x_i\ge a]\le b\)
  • D a b\(\sum_{i\in T}[y_i\le a]\le b\)
  • U a b\(\sum_{i\in T}[y_i\ge a]\le b\)

\(1\le n\le80,1\le x_i,y_i\le100,1\le v_i\le10^{15},1\le m\le320,1\le a_i\le100,0\le b_i<n\),且 \((x_i,y_i),(t_i,a_i),(t_i,b_i)\) 互不相同。

阅读全文 »

简介

给两个长度为 \(n\) 的序列 \(a_{0 \sim n-1}, b_{0 \sim n-1}\),FFT 可以在 \(O(n \log n)\) 的时间求出 \(c_k = \sum_{i+j = k}a_i \times b_j\),即多项式乘法。

在本篇 Blog 中,假定所有的 \(\mathbf{n}\) 都是 \(\mathbf{2}\) 的整数次幂。

阅读全文 »

生地很自闭,哭着回来搞 OI 了 >_<。

题意

\(\{a\},\{p\},\{k\}\),求解

\[ \left\{\begin{array}{ccc} a_1-x\cdot k_1 & \equiv & 0\pmod{p_1} \\ a_2-x\cdot k_2 & \equiv & 0\pmod{p_2} \\ & \vdots & \\ a_n-x\cdot k_n & \equiv & 0\pmod{p_n} \\ \end{array}\right. \]

阅读全文 »

简介

CRT 可以在 \(b_1\cdots b_k\) 两两互质时,解出形如

\[ \left\{\begin{array}{ccc} x & \equiv & a_1\pmod{b_1} \\ x & \equiv & a_2\pmod{b_2} \\ & \vdots \\ x & \equiv & a_k\pmod{b_k} \end{array}\right. \]

的方程组。

阅读全文 »