[矩阵快速幂]LOJ2128(HAOI2015)【数字串拆分】题解
题目概述你有一个长度为 $n$ 的数字串。定义 $f(S)$ 为将 $S$ 拆分成若干个 $1\sim m$ 的数的和的方案数，你可以将这个数字串分割成若干个数字（允许前导 $0$），将他们加起...
[拆系数FFT]洛谷4245【任意模数NTT】题解
题目概述求 $A(x)B(x)$ ，系数对任意模数 $p$ 取模。解题报告任意模数NTT好像需要三模数NTT搞。然而我不会NTT……所以我来愉快的讲一波任意模数FFT（雾）。其实洛谷里panda...
[区间DP]LOJ2063(HAOI2016)【字符合并】题解
题目概述有一个长度为 $n$ 的 $01$ 串，你可以每次将相邻的 $k$ 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 $k$ 个字符确定。你需要求出你能获得的最...
[状压DP+组合]LOJ2540(PKUWC 2018)【随机算法】题解
题目概述我们知道，求任意图的最大独立集是一类NP完全问题，目前还没有准确的多项式算法，但是有许多多项式复杂度的近似算法。例如，小C常用的一种算法是：对于一个 $n$ 个点的无向图，先等概率随机一...
[后缀数组+线段树]LOJ2064(HAOI2016)【找相同字符】题解
题目概述给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。解题报告先套路一波：把两个串接在一起（加个分隔符），求后缀数组...
[DP+组合]LOJ2538(PKUWC 2018)【Slay the Spire】题解
题目概述有 $n$ 张攻击牌（造成攻击牌数值的伤害）和 $n$ 张强化牌（攻击牌伤害均 $\times$ 强化牌数值），从中抽出 $m$ 张并选出最优秀的 $K$ 张打出，求所有方案造成的伤害之...
[拓扑+DP]LOJ2060(HAOI2016)【食物链】题解
题目概述给出 $n$ 个生物 $m$ 条能量流动，求食物链个数。解题报告脑子不好用了，划波水。生物题了解一下。食物链的开始通常是绿色植物（生产者）,从绿色植物开始至少要有三个营养级。书写食物链是...
[线段树]LOJ2529(ZJOI2018)【胖】题解
题目概述一条直线上有 $n$ 个点，只有相邻点之间有边。刚开始 $dis_i=10^{18}$ ，给出 $K$ 个关键点的 $dis$ ，用Bellman–Ford求最短路，令 $t$ 为每次最...
Codeforces Round #483(Div.2)题解
神tm结论大赛日神仙。A求中位数。#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[1...
[线段树动态开点+启发式合并]LOJ2537(PKUWC 2018)【Minimax】题解
题目概述一个节点 $i$ 的权值有 $p_i$ 的可能是儿子节点权值最大值，$1-p_i$ 的可能是儿子节点权值最小值（至多两个儿子），假设根节点(1)权值有 $m$ 种可能，第 $i$ 小的为...
