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)\)