link主要记录一下做题过程。首先题目看上去很不好处理，考虑从部分分的角度入手。先看\(m=n-1\)的部分分，这个性质让我们很容易想到一棵树。考虑把原材料当作点，菜品当作边，一道连接\((x,y)\)的菜品表示只能用编号为\(x\)和\(y\)的原材料。对于这棵树，我们每次选择一个叶子，

P6773[NOI2020]命运给你一棵\(n\)个节点的树，要给每条边染成\(0\)或\(1\)。有\(m\)个限制\((u,v)\)满足\(u\)是\(v\)祖先，表示\(u\)到\(v\)的路径中至少有一条边被染成了1。求方案数。\(n,m\le5\times10^5\)。首先会想到容斥，但是很没前途，所以考虑

Link题意给定一棵\(n\)个节点的有根树和\(m\)条祖先到后代的链。问有多少种把边权设置为\(0\)或\(1\)的方案使得每条链上至少有一条边是\(1\)。答案对\(998244353\)取模。\(1\leqn,m\leq5\times10^5\)题解我们将链的下端称为限制的起点。容易发现，对于同一

观察数据范围，\(T\)很大，\(n\)很小，用矩乘。对于一条边\((u,v,w)\)，我们将\(u\)拆成\(w-1\)个点，并连接\((u_0,u_1,0),(u_1,u_2,0)...(u_{w-2},u_{w-1},0)\)和\((u_{w-1},v_0,c_{v})\)，总点数\(5n\)。将美食节按时间排序，相邻两个美食节之间用矩阵快速幂转移，然后再加上附加

P6775NOI2020制作菜品给定正整数\(n\)，\(m\)，\(k\)。有一个\(m\)行\(k\)列网格，每个网格可以被涂上\(n\)种颜色之一，要求：一行最多出现两种颜色。第\(i\)种颜色必须恰好被使用\(a_i\)次。\(\{a_i\}\)给定，保证\(\suma_i=m\timesk\)。请构造涂色方案或判定不

美食家很显然可以写出矩阵。发现相当于有\(q\)次询问\(A^k\)，预处理矩阵的\(2^0,2^1,\cdots,2^w\)次幂然后用向量乘矩阵即可做到\(O(n^3\logT+qn^2\logT)\)。https://loj.ac/s/1758382命运没发现链是祖先-后代这样的，想了一年不会做有这个性质就可以直接dp了，然后线

分块。设分出来左散块\(A_1\)，中间块\(B_1,\cdots,B_k\)，右散块\(A_2\)。那么贡献有\(A_1\leftarrowA_1\)即散块对自己，\(A_1\leftarrowA_2\)即散块对散块，\(A_i\leftarrowB_j\)即散块对整块，\(B_i\leftarrowB_j(i\neqj)\)即整块对整块，\(B_i\leftarrowB_i\)即整块自己。

赛前才发现真题基本没做过/kkDay1美食家老经典题了，先写出一个dp，\(f[i,j]\)代表第\(i\)天在\(j\)号点的最大权值。转移显然，由于\(w\le5\)所以只需保留前\(5\)

链接：https://www.luogu.com.cn/problem/P6775题目描述：有\(m\)道菜，和\(n\)种原材料，每个原材料有一个质量\(d_{i}\),有\(\sum_{i=1}^{n}{d_{i}}=m\timesk\)(m为正整数)，每次

\(\mathcal{Link}\)比较智慧，但如果能想到链树的话其实不难。（为啥全机房都在刷Ynoi就我在搞思维题啊）考虑啥叫“只有有限棵树不能被表示出来”。可以发现，这等价于任意一

XSY押题！/se对于一类问题：有\(n\)种不同的饮料，第\(i\)种有\(a_i\)升。你需要把它们分到\(m\)个瓶子里面，每个瓶子容量为\(k\)，你的分配方案需要满足：每个瓶子都被

一道不错的题目。一个朴素的dp就是\(f_{i,x}\)表示时间\(i\)时从1走到\(x\)的最大美味值，就有转移\(f_{i,v_j}=\max\{f_{i-w_j,u_j}+c_{v_j}+美食节贡献\}\)，结