【省选十连测之九】【DP】【组合计数去重】【欧拉函数】基本题
- 题意:
- 输入格式:
- 输出格式:
- 数据范围:
- 思路:
- 嵌套题的转移
- 基本题的转移
- Part1
- Part2
- Part3
- 代码
题意:
这是一个关于括号组合的题。
首先定义一道题是由'(',')',',','!' (即左括号,右括号,逗号,感叹号)四种符号组成的。
然后我们再定义两种题型。
基本题:由若干个嵌套题(>=1个)组成,相邻的两套嵌套题之间由','(逗号)隔开。两道基本题被认为是相同的,当且仅当其中一个基本题的“嵌套题的序列”经过轮换之后能够得到另外一个基本题的“嵌套题的序列”。
嵌套题:由若干个基本题(>=1个)组成,相邻的两套基本题之间由'!'(感叹号)隔开,且在最外层有一对‘()’将整个序列包起来。两道嵌套题被认为是相同的,当且仅当其中一个嵌套题的“基本题的排列”经过全排列之后,其中的一个基本题的排列能够得到另外一个嵌套题的“基本题的排列”(即忽略顺序)。
现在的问题是,n对括号能够得到多少个不同的基本题?
输入格式:
第一行两个整数t,p,表示询问组数和模数。
接下来t行,每一行一个整数n表示能够使用的括号对数的总数。
输出格式:
对于每一个询问,输出一个整数表示由n对括号组成的基本题的数量模p的结果。
数据范围:
\(n<=250
首先这个题是一道DP+组合计数问题。 自己在考场上列了一堆DP式,然后wa得飞快... 然后开始进入正题。 我们令g[i][j]表示使用长度(即括号的对数)<=i的基本题组成总长度为j的嵌套题的方案数,t[i][j]表示使用长度等于i的基本题j道组成嵌套题的方案数。值得一提的是,其中的g[i][j]的第一维可以省掉(相当于滚动),体现在代码中就是CalcQT()中那个局部的f[]数组。 其中g[i-1][j]表示没有使用长度为i的基本题,后面部分就可以根据定义直接得出。又因为t[i][k]的定义直接就是组成嵌套题的方案数,而且是从小到大枚举的基本题的长度,所以就已经排除了顺序这一元素的影响了。 这一部分的大致思路是经过一个会算重的DP之后,再来利用欧拉函数进行去重。 先考虑简单的,也就是f[i][j][k]的转移。考虑第一层枚举一个数i表示当前使用的是长度为i的嵌套题,再从大到小枚举一层j表示总长度为j,然后枚举一层us表示使用了多少个长度为i的嵌套题,再枚举一层k>us表示使用了us个嵌套题后得到的简单题含有多少个嵌套题。就有转移: 这个式子是什么意思呢? 首先,非常感谢您能够有足够的耐心看到这里...但是不幸的是,难点就在这里出现了... f[i][j][k]实际上求出来的是一个使用了<=i的长度的嵌套题k道,一共使用了j对括号的基本题的方案数,但其实是一个全排列。 我们用不同的字母来表示不同的嵌套题,因为这个时候只和嵌套题的种类有关了,可以先抛去括号总数这一维不管了。 那应该怎么做呢? 懵了没事,先强忍着看完转移,后面会举例子来帮助理解的。 转移的话,我们先枚举一共有i对括号(注意后面的f[][]是已经省去了第一维的数组),然后再枚举一共有j个嵌套题,然后初始化一个s=0,再枚举分成了k个循环节,当且仅当i%k0&&j%k0等于0的时候,将\(f[i/k][j/k]*\phi(k)\)累加到s里面。最后完成了k这一层的枚举之后,将s累计到jb[i]里面即可。 是不是有点懵了? 怎么样,这个例子对于你是否有一定的帮助呢?可以结合例子和前面的转移一起看一下。 如果你已经成功的攻克了上面一个难题了,那么恭喜你,你还差最后一个问题就能够获得最终的胜利了! 其实这一点应该列在全局里面的。你是否还记得一个数组,就是t[i][j]?我猜你应该还记得,它又是怎么转移的呢? 考虑如何计算这个东西。因为嵌套题是忽略顺序的,其实就变成了一个组合问题了。一共有jb[i]个长度为i的基本题,然后用这jb[i]个基本题组合成总个数为j的嵌套题。考虑第i种基本题用了\(x_i\)次。然后就有等式: 其中\(x_i\)可以为0,然后求解的个数。这不是就是组合问题的经典模型吗?那么直接有结论: 但是jb[i]太大了,但是我们可以考虑递推求这个东西。也就是: 然后就可以外层枚举一个i,然后内层枚举j,就可以递推了。 是不是很开心呢?思路:
巨恶心
最后发现大样例里竟然有n<=10的答案!!!直接打表
其实后来发现自己和solution的DP定义其实差不多...但是转移的确是想得太简单了。
首先我们定义qt[i]表示使用i对括号的嵌套题有多少个,jb[i]表示使用i对括号的基本题有多少个。嵌套题的转移
我们枚举一个总长度n,然后再从小到大枚举i,然后总大到小枚举一个总长度j(放在第二层枚举主要是为了使得转移的时候使用的是上一层,即g[i-1][]的数值),再枚举一下当前长度为i的基本题用了k个,还要保证i*k<=j。然后就有转移式:
然后考虑这个时间复杂度。前面三个循环的枚举都是\(O(n)\)的,最后一层是一个调和级数,也就是最后一层平摊下来是\(O(\log n)\)的,合起来就是\(O(n^3\log n)\)的。基本题的转移
这个和上面嵌套题的转移的难度就不是一个数量级的了...首先定义f[i][j][k],表示使用了长度小于等于i的嵌套题k个,组成了总长度为j的基本题,而且轮换之后不视作同一道基本题的方案数。可以发现这个绝对不是答案。同时,这里的第一维i仍然可以通过之前求g[][]的技术省略掉。Part1
大致就是,前面一半还是表示不用长度为i的嵌套题,后面一半就是要考虑先构造一个含有us道嵌套题的序列(\(qt[i]^{us}\)),然后k中的us个提出来就是这个序列(也可以想成是把这个序列插进之前已经有的嵌套题序列中去)(\(C_{k}^{us}\))。然后就可以转移啦!时间复杂度大致同上。Part2
然后我们有一个很naive的想法,就是因为它是一个轮换,就像是一个圆排列一样,考虑像圆排列一样除以一个k,但是这样子明显除多了...(因为我考试的时候就是这么想的...)
下面是一个例子:
然后有一个序列ABABAB,它和另外一个序列重复计算了,是谁呢?就是BABABA。然后我们是直接除以总的嵌套题数量,也就是除以6,但其实我们应该除以2,因为这一只有两个被算重了,然后我们就除多了。
我们考虑一个含有j个嵌套题的序列,它的最小循环节有x个嵌套题,然后一共有k个最小循环节,那么有\(x*k=j\),然后再我们发现这个序列我们应当除以x(轮换超过一个循环节之后,本来就没有重复计算了),但实际上我们除以的是j=x*k,多除了一个k。那么我们考虑将这个k事先乘上去,然后就可以最后统一除以j了。怎样才能够事先乘上去呢?可以使用欧拉函数\(\phi(n)\)。因为我们有一个结论\(\sum_{d|n}^{n}\phi(d)=n\),可以将一个总的有k个嵌套题的序列乘上\(\sum_{d|k}^{k}\phi(d)\)就可以了。
拿上面的例子来说说吧。
ABABAB的话,x=2,k=3,j=xk=6。然后当枚举k=1的时候,进来一次,累加到s里面的是\(f[tot/1][6/1]*\phi(1)\),然后就可以发现ABABAB和BABABA是包含在\(f[tot/1][6/1]\)里面的,都乘上了一个phi(1)=1。当枚举到k=3的时候,又会在s里面累加一个\(f[tot/3][6/3]*\phi(3)\)。这个时候ABABAB和BABABA还是都包含在f[tot/3][2]里面的,相当于是两者的系数都加上了一个phi(3)=2。到最后,我们会惊奇的发现,ABABAB和BABABA这两个式子的前面的系数都是(1+2)=3=k,又因为这两个排列应该合在一起考虑,那么总的系数就是23=xk=j,然后最后再统一除以一个j,就解决问题啦!Part3
应该还记得定义是:使用j个长度为i的基本题组成的嵌套题的方案数。
恭喜你,你通过了这道题!代码
#include