目录
CF1956F Nene and the Passing Game
题目大意
给定 \(n\) 个点，每个点有两个系数 \([l_i,r_i]\)。若 \(i,j(r>i)\) 两点有边，当且仅当满足 \(l_i+l_j\le j-i\le r_i+r_j\) 。问该图有几个连通块
solution
先进行简单的化简：
\[l_i+i\le j-l_j\and j-r_j\le r_i+i \]于是题目转化为每个点有两种区间 \([i-r_i,i-l_i],[i+l_i,i+r_i]\)，那么联通的判定就为两个的点的不同种区间有交
我们发现如果问题是 两个的点的区间有交，那么是简单的，我们建立3n个虚点，用并查集维护，对于一个区间，只对 \(i\to i+1\) 合并
那么如何处理不同种区间，题解提供了一种非常优秀的做法：对于一个虚点，如果只含有一种区间，我们就把它删掉，否则它们一定互相联通（易证）
CF1942E Farm Game
题目大意
有一个长度为 \(l\) 的数列，有两个人，每个人有 \(n\) 颗棋子，保证两人的棋子是交错排布的。
每次操作可以选择 \(k(k\ge 1)\) 颗棋子，若它们的左/右边没有棋子或边界，就把它们向左/右边移动一格。
问先手必胜的情况数
solution
一共有 \(\binom l {2n}\) 种情况
首先考虑充要，如果成对的两颗棋子距离差有偶数，先手必胜
考虑计数，枚举放在两颗棋子中间的数量，那么就是插板法
CF1942G Bessie and Cards
题目大意
你有 \(5\) 张特殊卡， \(a\) 张 0 类卡，\(b\) 张 1 类卡，\(c\) 张 2 类卡。
随机排成一堆后，你先从上面摸 \(5\) 张卡，然后每次打出一张 \(x\) 类卡，并再摸 \(x\) 张卡，直到抽取次数用完或者牌堆清空为止。
你不能出特殊卡。问有多少概率将所有特殊卡全抽到。
solution
我们考虑 \(1\) 类卡没用，然后把题目转变成：有 \(a\) 个 \(-1\)，\(c\) 个 \(1\) ，5个特殊的 \(-1\)，要求把它们排列起来，保证最后一个特殊的 \(-1\) 及其之前的每个前缀和都大于5
于是我们考虑格路计数，设 \(f_{i,j}\) 为用了 \(i\) 个 \(-1\)，\(j\) 个 \(1\)，那么我们可以将题目转化为起点为 \((0,4)\)，且不能穿过 \(x=y\) ，到达 \((i,j+4)\) 的方案数，即 \(\binom{x+y}y-\binom{x+y}{y+5}\)
那么我们需求统计两种情况的答案
- 用完了全部的贡献 \(f(a+5,c)\binom{a+5}5\)
- 用了 \(x+5\) 个 \(-1\)，\(x\) 个 1，且最后一个为 \(-1\) 的方案： \(f(x+4,x)\binom {x+5} 5\binom{a+c-x-x}{a-x}\)
最后除以总方案数 \(\frac{(a+c+5)!}{a!c!5!}\)
tips
考虑一下为什么不会算重，我们的第二种是到了前缀和为0才计数，那么出来最后到0的情况，就只剩下把全部用完的情况，不重也不漏
CF1943D2
题目大意
给一个长度为 \(n\) 的非负整数序列 \(a_i\)。可以进行若干次操作，每次操作选择一对 \(l,r\) 满足 \(1\leq l<r\leq n\)，将区间 \(a[l,r]\) 都减去 \(1\)。如果一个序列可以通过若干次操作变成全 \(0\) 数列，则我们认为这个数列是好的。
给定 \(n,k,p\)，求所有长度为 \(n\)，值域 \(\in[0,k]\) 的序列有多少个是好的，对 \(p\) 取模。保证 \(p\) 是质数。
\(3\leq n\leq 3000, 1\leq k\leq n,\sum n^2\leq 10^7\)。
solution
先考虑D1，考虑设两个位置填了什么，状态数为 \(O(nk^2)\)，用前缀和优化可以使时间复杂度一致
发现没有什么优化空间
E3. Trails
题目大意
有 \(m\) 个点，每个点有两个参数 \(x_i,y_i\)，点 \(i\to j\) 的路径数量为 \(x_ix_j-y_iy_j\)（这里经过了简单的转化，即 \(x_i=s_i+l_i,y_i=l_i\)）。你从点 \(1\) 出发，问走 \(n\) 步的路径方案数。
solution
首先可以想到dp，设 \(f_{i,j}\) 表示第 \(i\) 天到了点 \(j\) 的方案数，转移：
\[f_{i,j}=\sum_{k=1}^n f_{i-1,k} (x_jx_k-y_jy_k) \]这就是E1，将它矩阵乘法就是E2
但是E3我们要考虑进行一点变化
\[f_{i,j}=x_j\sum f_{i-1,k}x_k-y_k\sum f_{i-1,k} y_k \]我们设 \(A=\sum f_{i-1,k}x_k,B=\sum f_{i-1,k}y_k\)
于是可以得到转移
\[\begin{align} A&=\sum_j f_{i,j}x_j\\ &=\sum_jx_j(x_jA'-y_jB')\\ &=A'\sum x_i^2-B'\sum x_iy_i\\ B&=A'\sum x_iy_i-B'\sum y^2_i\\ \end{align} \]于是我们可以只转移AB，然后计算答案，同样是矩乘，\(O(8\log n)\)
标签：题目,sum,CF,solution,VP,leq,大意,binom,小记 From： https://www.cnblogs.com/zhy114514/p/18258906