计数练习

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\)是否往后指

这个跑出来的东西我们可以用背包容斥