lzx20120124

摘要： 题目。 做法1（人类智慧） 原题。 我们观察一下 \(n\) 在 \([1,4]\) 时的系数情况，如果你是纯手推的话应该可以观察出递推式来。 当 \(m<=n\) 时： \(ans_i=a_i*i*(-1)^{i+1}+ \sum_{j=1}^{i-1}ans_{i-j}*a_j*(-1)^{j+ 阅读全文

摘要： 题目。 赛时做法（瞎搞）: 我们把 \([3,10^6]\) 内的素数筛出来，对于 \(p'\) 它仍有可能是答案的必要条件是 \(\left(\frac{a}{p}\right) = \left(\frac{a}{p'}\right)\)。 然后我们不断的进行筛，直到筛出答案。 只有 17 次询问 阅读全文

摘要： 题目：求把 \(n\) 分为若干个可重复的正整数之和的 mod m 方案数（分拆数）。 思路 首先 \(O(N^2)\) 背包显然，然后你可以根号分治优化到 \(O(N \sqrt N)\) ，这里直接推式子。 设 \(P(n)\) 表示 \(n\) 的拆分数方案（及答案）。 \(\sum_{i=1 阅读全文

摘要： 题目 自己写的必须要写题解啊！ 先考虑什么是期望轮数。 显然可以从样例观察到。 轮数的概率 \(P\) 是知道的（为 \(\frac {合法的}{总数}\)），且每次操作都是独立的（合法表示 \(b\) 有序可以结束算法）。 那么若第一次就成功次数为 \(1\)。 若第一次失败，那么由于操作是独立的 阅读全文

摘要： 题目 思路 非平局回合数\(k\)是不好求的，我们考虑先求钦定非平局回合数为\(k\)的数量。 这可以直接树形 dp，设 \(dp_{u,j}\)表示\(u\)为根节点钦定非平局回合数\(k\)的数量。 转移很简单直接树上背包即可，时间复杂度\(O(N^2)\)。 时间复杂度证明 求出了 dp 后， 阅读全文

摘要： 其实只需一句话：任意两个点都只会在 lca 上被合并，而 lca 是唯一的，所以时间复杂度是 \(N*(N-1)/2\) 也就是\(O(N^2)\)。 但我想到了另一种或许更简单的证明。 我们先考虑一条链，那么可以通过自己计算得到有\(1+……+N-1\)。 然后考虑不断加点，但是加点需要保证从下到 阅读全文

摘要： 题目。 注意到 \(n \le 4\) 且 \(m\) 也不大考虑直接分讨主要是通项的我也不会 这里直接用最基础的方法推式子韦达我也不会 设 \(ans_{i}=\sum_{j=1}^{n}a_{j}^i\) $n=1$时 $ans_{m}=a_{1}^m$ $n=2$时 当 $m=0$ 时 $an 阅读全文

摘要： 题意 给你一个长度为的序列 \(a\) \(m\) 次询问 有三种操作： 1. 问区间最大值减去第一个元素的值 2. 交换两个元素 3. 给 \(l,r,t\) 对于区间 \(l,r\) 中第 \(x\) 个元素加上 \(x \times t\) \(n,m<=1e5\) \(0=<t<=1e4\) 阅读全文