博客食用更佳 https://www.cnblogs.com/czyty114/p/14678032.html

B

$\;$

题意

$\;$
给定一个长度为$n$的初始序列$A$
可以进行任意多次操作，每次操作可以选定一个正整数$x$，将所有值$\geq x$的数减一
问最终可以得到的序列有多少种
$n\leq 10^5,a_i\leq 10^9$
input
2
1 2
output
4
$\;$

Solution

$\;$
将初始序列不降排序之后，显然每次操作会将一段后缀的值减去1
你会发现一个很重要的性质：相邻两个数的差只会变小或不变，一定不会变大。
所以，如果我们如果得到了一个序列$B$，满足$\forall 1 \leq i \leq n, B_i-B_{i-1} \leq A_i - A_{i-1}$
一定可以构造出一种操作方案，使得$A$变成$B$
令$A_0=0$
因此：
$$Ans = \prod_{i=1}^n (a_i-a_{i-1}+1)$$
$\;$

C

题意

$\;$
给定一个长度为$n$的字符串s，只有W,R,B三种字符，分别代表白、红、蓝。
初始时，一排$n$个方格按照字符串涂好颜色，然后按照金字塔的形状不断向上摞方格。
规则是这样的：
如果相邻的两个颜色都为x，会摞上一个颜色为x的方格。
否则会摞上一个和这两个方格颜色都不同的方格。
问最顶端的方格颜色
$n\leq 4 \times 10^5$
input
RRBB
output
W
$\;$

Solution

$\;$
思维好题。
不妨将三种颜色分别设为0，1，2
假设相邻两个方格颜色为$a, b$，那么摞上的方格的颜色将为：
$$-(a+b)\;(mod \;3)$$
$\;$
所以和杨辉三角一样不断往上加，可以手推一下。
发现顶端的值为
$$(-1)^{n-1} \times \sum_{i=0}^{n-1} C_{n-1}^i s_i\; (mod \; 3)$$
$\;$
因为阶乘可能是3的倍数，所以不大好处理逆元。
可以使用Lucas定理轻松解决
Lucas: 若$p$是质数，$C(n,m) = C(n/p,m/p) \times C(n\%p,m\%p)$
时间复杂度：$O(n\;log\;n)$
$\;$

E

$\;$

题意

$\;$
问有多少个长度为$2n$的序列$A$满足以下条件：
1.恰好有$n$个1和$n$个-1
2.恰好有$k$个$(l,r)$，满足$a_l+a_{l+1}+\cdots +a_r = 0$
$n\leq 30, k\leq n^2$
input
3 7
output
6
$\;$

Solution

$\;$
又是计数dp题
前缀和转化一下比较显然。
如果只是简单的从前往后做，考虑是+1还是-1的话是不行的。
不妨先考虑$s_i$全部非负的情况。
$dp_{i,j,k}$表示当前填了$i$个数，且有$j$个$(l,r)$满足条件，目前填的数中$hole$的数量为$k$的方案数。
$hole$表示序列中相邻两个元素值相同之间的空隙。
由于我们最终的$s$序列一定是波浪的形状。
所以一次转移会加入一些相同数值的元素$val$，插入到这些空隙中（包括序列最左最右）
且这$k+2$个位置必须都要有$val$这个数
这样转移的好处是既方便去统计$(l,r)$的个数，还能保证这个序列这个序列是合法的。
假设填了$x$个数
那么转移就是$dp_{i+x,j+\frac{x(x+1)}{2},x-(k+2)}=dp_{i,j,k} \times C_{x-1}^{k+1}$
这个组合数可以用插板的思想去想。
最终统计答案时，我们把序列分为两部分：非负和负的。
而上下两部分都是满足刚刚dp的东西的。
所以直接乘法原理。
即：枚举$(x,y,z)$ 答案加上$dp_{x,y,z}\times dp_{2n+1-x,k-y,z-1}$
时间复杂度：$O(n^5)$