博客食用更佳 https://www.cnblogs.com/czyty114/p/14678032.html
B
题意
给定一个长度为n的初始序列A
可以进行任意多次操作,每次操作可以选定一个正整数x,将所有值≥x的数减一
问最终可以得到的序列有多少种
n≤105,ai≤109
input
2
1 2
output
4
Solution
将初始序列不降排序之后,显然每次操作会将一段后缀的值减去1
你会发现一个很重要的性质:相邻两个数的差只会变小或不变,一定不会变大。
所以,如果我们如果得到了一个序列B,满足∀1≤i≤n,Bi−Bi−1≤Ai−Ai−1
一定可以构造出一种操作方案,使得A变成B
令A0=0
因此:
Ans=n∏i=1(ai−ai−1+1)
C
题意
给定一个长度为n的字符串s,只有W,R,B三种字符,分别代表白、红、蓝。
初始时,一排n个方格按照字符串涂好颜色,然后按照金字塔的形状不断向上摞方格。
规则是这样的:
如果相邻的两个颜色都为x,会摞上一个颜色为x的方格。
否则会摞上一个和这两个方格颜色都不同的方格。
问最顶端的方格颜色
n≤4×105
input
RRBB
output
W
Solution
思维好题。
不妨将三种颜色分别设为0,1,2
假设相邻两个方格颜色为a,b,那么摞上的方格的颜色将为:
−(a+b)(mod3)
所以和杨辉三角一样不断往上加,可以手推一下。
发现顶端的值为
(−1)n−1×n−1∑i=0Cin−1si(mod3)
因为阶乘可能是3的倍数,所以不大好处理逆元。
可以使用Lucas定理轻松解决
Lucas: 若p是质数,C(n,m)=C(n/p,m/p)×C(n%p,m%p)
时间复杂度:O(nlogn)
E
题意
问有多少个长度为2n的序列A满足以下条件:
1.恰好有n个1和n个-1
2.恰好有k个(l,r),满足al+al+1+⋯+ar=0
n≤30,k≤n2
input
3 7
output
6
Solution
又是计数dp题
前缀和转化一下比较显然。
如果只是简单的从前往后做,考虑是+1还是-1的话是不行的。
不妨先考虑si全部非负的情况。
dpi,j,k表示当前填了i个数,且有j个(l,r)满足条件,目前填的数中hole的数量为k的方案数。
hole表示序列中相邻两个元素值相同之间的空隙。
由于我们最终的s序列一定是波浪的形状。
所以一次转移会加入一些相同数值的元素val,插入到这些空隙中(包括序列最左最右)
且这k+2个位置必须都要有val这个数
这样转移的好处是既方便去统计(l,r)的个数,还能保证这个序列这个序列是合法的。
假设填了x个数
那么转移就是dpi+x,j+x(x+1)2,x−(k+2)=dpi,j,k×Ck+1x−1
这个组合数可以用插板的思想去想。
最终统计答案时,我们把序列分为两部分:非负和负的。
而上下两部分都是满足刚刚dp的东西的。
所以直接乘法原理。
即:枚举(x,y,z) 答案加上dpx,y,z×dp2n+1−x,k−y,z−1
时间复杂度:O(n5)