计数练习
CF840C On the Bench
考虑\(xy,xz\)是完全平方数,\(yz\)同样也是
于是我们可以对此划分等价类,每个等价类里的数不能相邻
我们发现在插入一个等价类后一些不合法的也可能变合法,因此我们这里要记录一些不合法的信息
考虑\(dp_{i,j}\)表示前\(i\)个等价类中有\(j\)个不合法的对,这里先在等价类里消序
考虑插入了\(x\)个数,我先把他们放一起,然后砍\(i\le x-1\)刀
考虑枚举\(p\le min(i+1,j)\)为放入不合法对的段即可
时间复杂度是\(n(\sum a_i)^2\)
似乎有\(log\)的多项式
[CTSC2017]吉夫特
直接\(Lucas\),然后你会发现\(i+1\)是\(i\)的子集
然后呢,因为每个数的大小不一样,可以直接枚举值,枚举它的子集刷表就行了
[AGC009C]Division into Two
考虑对序列划分成若干个连续段,每个连续段都放入\(A\)或\(B\)
设\(dp_{i,0}\)为第\(i\)位放\(A\),且前面放\(B\),\(1\)同理
然后你会发现\(dp_{i,0}=\sum_{j\in[L,R]}dp_{j,1}\),这个\(L\)保证\([L,i-1]\)的\(B\)满足条件,\(R\)保证\(S_i-S_{R-1}\ge A\),都可以二分求
最后的答案可以在后面放一个极大值统计
CF1383E Strange Operation
一个非常有意思的题
可以发现我们的操作等价于在连续的\(0\)段删一个,或在连续的大小\(>1\)的\(1\)段删一个
我们考虑记录一个序列\(A\)为原串每对相邻\(1\)中\(0\)的个数,这里我们在开头和结尾都放一个\(1\)
可以发现这个\(A\)和原串一一对应
然后操作在\(A\)就体现为\(A_i-1\)或直接删除一个\(A_i=0\)的\(i\)
一个合法的由\(A\)操作出来的\(B\)满足除开头结尾,中间的序列可以在\(A\)上找到一个子序列使\(A_{p_i}\)都大于\(B_i\)
然后如果要对\(B\)记数,不难想到\(A,B\)匹配,对\(A\)\(dp\)但\(A,B\)可以匹配的位置有很多
这里我们贪心地让\(B\)找最前面\(A_x>B_i\)的\(x\),这样如果\(B\)是合法的一定是找得到的,并且唯一
直接\(dp_i\)表示\(B\)匹配了\(A_i\),填了\(y\),不难想到\(j\Rightarrow i\)只需满足\(x\in[j+1,i]\)没有\(A_x>y\)的
这里对\(y\)直接维护最大的\(j\)即可
[AGC043B] 123 Triangle
降职了
手玩一下就会发现这个\(3\)是不会作为答案的
如果第一次差分后出现\(1\),那最后的答案只能是\(1/0\),因为\(0,2\)碰到\(1\)都会变成\(1\),最后的答案一定会消去\(2\)
我们直接对序列\(\bmod 2\),然后减法变加法
观察到\(f_{i,j}=f_{i-1,j}+f_{i-1,j+1}\)
这个很想杨辉三角的形式,事实是这个的系数是\(\binom{i-1}{n-1}\)
然后直接用\(Lucas\)算就好了
如果没有\(1\),直接\(/2\)即可
[HNOI2011] 卡农
这个偶数的条件并不是很好处理如果是抽象为二进制串复杂度起飞
这里提出一个大胆的\(dp\)设计
设\(dp_i\)为前\(i\)个位置满足条件的方案,这里我们钦定每个串之间是有顺序的
因为知道了前\(i-1\)个那第\(i\)个也是可以直接推出来的,这里我们先不考虑不合法的方案,总方案为\(A_{2^n-1}^{i-1}\)
考虑不能为空等价于前\(i-1\)不能满足条件,即要减去\(dp_{i-1}\)
再考虑第\(i\)个不能和前面的一个\(j\)相同,那就等价与\(i-2\)就满足条件
也就是\(dp_{i-2}(i-1)(2^n-1-(i-2))\),可以发现这样前\(i-1\)一定是不合法的,因此和上面的没有算重
然后最后就完了,甚至不须考虑偶数位的限制
[AGC043D] Merge Triplets
成小丑了
首先不难看出这个题我们最后得出的序列是大致单调递增的,只有大概\(3\)个跟在单调子序列其其中的\(i\)后面
然后\(dp\),委了,因为每个数后面跟\(2\)个数的块要小于等于\(1\)的块数
如果把这个也设计进状态就好像会超时
然后\(nb\)的地方来了
设\(dp_{i,j}\)为前\(i\)个位置\(2\)的块数减\(1\)的块数为\(j\)且只考虑\(i\)以内的数
枚举最后一个的大小为\(1,2,3\)
然后你会发现大小为\(2\)时我们直接调整\(i-1\)里的数,放一个在\(i\),\(i-1\)放\(i\)即可,因为\(i\)一定时最大的
\(3\)的也同理
[AGC052C] Nondivisible Prefix Sums
这个如果没有重排的条件,不难发现这里我们可以直接\(dp\)
但这里的重排就把每个序列特殊化了
首先我们的序列全部乘上\(x\)肯定是不会影响它的好坏的
这里先剔除\(Sum\bmod P\equiv0\)的
考虑找出\(x\)是众数,考虑对整个序列乘一个\(x^{-1}\),这里就只剩下\(1\)最多
结论:\(1\)的个数小于等于\(\sum\limits_{i=1}^{k}(P-B_i)+P-1\),\(B\)是所有非\(1\)数组成的序列是原题的充要条件
必要性不难证
对于充分性,我们考虑这样重排序列
取出当前序列的众数\(x\)
如果\(Sum+x\bmod P\equiv 0\),就找另一个数\(y\)来填,否则就用\(x\)填
唯一冲突的时候就是只有\(x\)的时候且\(x\ge2\)
我们可以发现如果众数变了,那么一定不会出现上述情况,因为相当于交替取数
所以对于众数一直是\(1\)的情况,可以发现我们只需要在用\(B_i\)后面填一下即可,最前面填\(P-1\)个
然后我们计数的话就考虑先选那些\(Sum\not\equiv(0)(\bmod P)\)的,再考虑剔除不合法的
然后我们设\(dp_{i,j}\)为选了\(i\)个非\(1\)的数,和为\(j\),转移就是背包
然后我们直接枚举每个\(i,j\),不合法的就是\(n-i>j+P-1\),注意\(n-i-j\not\equiv0(\bmod P)\)
[ABC214G] Three Permutations
被\(yjx\)教育了/kk
考虑只有一个序列\(P\),很明显就是错排
如果有两个序列,我们同样可以枚举冲突的数量容斥,问题在于冲突的位置可以是与\(P_i\)也可以是与\(Q_i\)
如果我们考虑\(P_i,Q_i\)连边,把冲突看作一条边,那我们就可以给边定向
进一步,这个\(P_i\),\(Q_i\)连边连出来的就是若干个环,我们可以在环上跑\(dp\)
这个\(dp\)模型很经典,\(dp_{i,j,0/1,0/1}\)为前\(i\)个选\(j\)条冲突边,\(i\)是否往前指,\(1\)是否往后指
这个跑出来的东西我们可以用背包容斥