【省选十连测之九】【DP】【组合计数去重】【欧拉函数】基本题

时间:2024-01-16 11:26:56

题意:

这是一个关于括号组合的题。

首先定义一道题是由'(',')',',','!' (即左括号,右括号,逗号,感叹号)四种符号组成的。

然后我们再定义两种题型。

基本题:由若干个嵌套题(>=1个)组成,相邻的两套嵌套题之间由','(逗号)隔开。两道基本题被认为是相同的,当且仅当其中一个基本题的“嵌套题的序列”经过轮换之后能够得到另外一个基本题的“嵌套题的序列”。

嵌套题:由若干个基本题(>=1个)组成,相邻的两套基本题之间由'!'(感叹号)隔开,且在最外层有一对‘()’将整个序列包起来。两道嵌套题被认为是相同的,当且仅当其中一个嵌套题的“基本题的排列”经过全排列之后,其中的一个基本题的排列能够得到另外一个嵌套题的“基本题的排列”(即忽略顺序)。

现在的问题是,n对括号能够得到多少个不同的基本题?

输入格式:

第一行两个整数t,p,表示询问组数和模数。

接下来t行,每一行一个整数n表示能够使用的括号对数的总数。

输出格式:

对于每一个询问,输出一个整数表示由n对括号组成的基本题的数量模p的结果。

数据范围:

\(n<=250<p<2^{30},t<=250\)

思路:

首先这个题是一道DP+组合计数问题。巨恶心

自己在考场上列了一堆DP式,然后wa得飞快...

最后发现大样例里竟然有n<=10的答案!!!直接打表

其实后来发现自己和solution的DP定义其实差不多...但是转移的确是想得太简单了。

然后开始进入正题。

首先我们定义qt[i]表示使用i对括号的嵌套题有多少个,jb[i]表示使用i对括号的基本题有多少个。

嵌套题的转移

我们令g[i][j]表示使用长度(即括号的对数)<=i的基本题组成总长度为j的嵌套题的方案数,t[i][j]表示使用长度等于i的基本题j道组成嵌套题的方案数。值得一提的是,其中的g[i][j]的第一维可以省掉(相当于滚动),体现在代码中就是CalcQT()中那个局部的f[]数组。

我们枚举一个总长度n,然后再从小到大枚举i,然后总大到小枚举一个总长度j(放在第二层枚举主要是为了使得转移的时候使用的是上一层,即g[i-1][]的数值),再枚举一下当前长度为i的基本题用了k个,还要保证i*k<=j。然后就有转移式:

\[g[i][j]=g[i-1][j]+g[i-1][j-i*k]*t[i][k]
\]

其中g[i-1][j]表示没有使用长度为i的基本题,后面部分就可以根据定义直接得出。又因为t[i][k]的定义直接就是组成嵌套题的方案数,而且是从小到大枚举的基本题的长度,所以就已经排除了顺序这一元素的影响了。

然后考虑这个时间复杂度。前面三个循环的枚举都是\(O(n)\)的,最后一层是一个调和级数,也就是最后一层平摊下来是\(O(\log n)\)的,合起来就是\(O(n^3\log n)\)的。

基本题的转移

这一部分的大致思路是经过一个会算重的DP之后,再来利用欧拉函数进行去重。

这个和上面嵌套题的转移的难度就不是一个数量级的了...首先定义f[i][j][k],表示使用了长度小于等于i的嵌套题k个,组成了总长度为j的基本题,而且轮换之后不视作同一道基本题的方案数。可以发现这个绝对不是答案。同时,这里的第一维i仍然可以通过之前求g[][]的技术省略掉。

Part1

先考虑简单的,也就是f[i][j][k]的转移。考虑第一层枚举一个数i表示当前使用的是长度为i的嵌套题,再从大到小枚举一层j表示总长度为j,然后枚举一层us表示使用了多少个长度为i的嵌套题,再枚举一层k>us表示使用了us个嵌套题后得到的简单题含有多少个嵌套题。就有转移:

\[f[i][j][k]=f[i-1][j][k]+f[i-1][j-us*i][k-us]*C_k^{us}*qt[i]^{us}
\]

这个式子是什么意思呢?

大致就是,前面一半还是表示不用长度为i的嵌套题,后面一半就是要考虑先构造一个含有us道嵌套题的序列(\(qt[i]^{us}\)),然后k中的us个提出来就是这个序列(也可以想成是把这个序列插进之前已经有的嵌套题序列中去)(\(C_{k}^{us}\))。然后就可以转移啦!时间复杂度大致同上。

Part2

首先,非常感谢您能够有足够的耐心看到这里...但是不幸的是,难点就在这里出现了...

f[i][j][k]实际上求出来的是一个使用了<=i的长度的嵌套题k道,一共使用了j对括号的基本题的方案数,但其实是一个全排列。

然后我们有一个很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)\)就可以了。

懵了没事,先强忍着看完转移,后面会举例子来帮助理解的。

转移的话,我们先枚举一共有i对括号(注意后面的f[][]是已经省去了第一维的数组),然后再枚举一共有j个嵌套题,然后初始化一个s=0,再枚举分成了k个循环节,当且仅当i%k0&&j%k0等于0的时候,将\(f[i/k][j/k]*\phi(k)\)累加到s里面。最后完成了k这一层的枚举之后,将s累计到jb[i]里面即可。

是不是有点懵了?

拿上面的例子来说说吧。

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

其实这一点应该列在全局里面的。你是否还记得一个数组,就是t[i][j]?我猜你应该还记得,它又是怎么转移的呢?

应该还记得定义是:使用j个长度为i的基本题组成的嵌套题的方案数。

考虑如何计算这个东西。因为嵌套题是忽略顺序的,其实就变成了一个组合问题了。一共有jb[i]个长度为i的基本题,然后用这jb[i]个基本题组合成总个数为j的嵌套题。考虑第i种基本题用了\(x_i\)次。然后就有等式:

\[x_1+x_2+x_3+...+x_{jb[i]}=j
\]

其中\(x_i\)可以为0,然后求解的个数。这不是就是组合问题的经典模型吗?那么直接有结论:

\[C_{jb[i]+j-1}^{j}
\]

但是jb[i]太大了,但是我们可以考虑递推求这个东西。也就是:

\[\frac{C_{jb[i]+j-1}^{j}}{C_{jb[i]+j-2}^{j-1}}=\frac{jb[i]+j-1}{j}
\]

然后就可以外层枚举一个i,然后内层枚举j,就可以递推了。

是不是很开心呢?

恭喜你,你通过了这道题!

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 250
using namespace std;
int inv[MAXN+5],C[MAXN+5][MAXN+5],phi[MAXN+5];
int qt[MAXN+5],jb[MAXN+5];
int MO,f[MAXN+5][MAXN+5],t[MAXN+5][MAXN+5];
int PowMod(int a,int b)
{
int ret=1;
while(b)
{
if(b&1)
ret=1LL*ret*a%MO;
a=1LL*a*a%MO;
b>>=1;
}
return ret;
}
int gcd(int a,int b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
void CalcQT(int n)
{
static int f[MAXN+5];\\就是g[][]
for(int i=1;i<=n;i++)
f[i]=0;
f[0]=1;//转移的解释见前
for(int i=1;i<n;i++)
for(int j=n-1;j>=1;j--)
for(int k=1;i*k<=j;k++)
f[j]=(1LL*f[j]+1LL*f[j-i*k]*t[i][k])%MO;
qt[n]=f[n-1];//嵌套题本身在外层还要加一对括号
}
void CalcJB(int i,int n)
{
for(int j=n;j>=1;j--)
for(int pw=qt[i],us=1;i*us<=j;us++,pw=1LL*pw*qt[i]%MO)
for(int k=us;k<=j;k++)
f[j][k]=(1LL*f[j][k]+1LL*f[j-us*i][k-us]*C[k][us]%MO*pw)%MO;//转移解释见前
for(int j=1;j<=i;j++)
{
int s=0;
for(int k=1;k<=j;k++)
if(j%k==0&&i%k==0)
s=(1LL*s+1LL*f[i/k][j/k]*phi[k])%MO;//累加phi到s中,f[i/k][j/k]就是一段内的方案数
jb[i]=(1LL*jb[i]+1LL*s*inv[j])%MO;//总体除以j
}
}
void Prepare()
{
//逆元、组合数、欧拉函数都暴力求
for(int i=1;i<=MAXN;i++)
inv[i]=PowMod(i,MO-2);
C[0][0]=f[0][0]=1;
for(int i=1;i<=MAXN;i++)
{
C[i][0]=1;phi[i]=0;
for(int j=1;j<=i;j++)
C[i][j]=(1LL*C[i-1][j]+1LL*C[i-1][j-1])%MO,phi[i]+=(gcd(i,j)==1);
}
for(int i=1;i<=MAXN;i++)
{
CalcQT(i);//计算qt[i]
CalcJB(i,MAXN);//计算jb[i]
t[i][0]=1;//递推求t[][]
for(int j=1;j<=MAXN;j++)
t[i][j]=1LL*t[i][j-1]*(1LL*jb[i]+1LL*j-1LL)%MO*inv[j]%MO;
}
}
int main()
{
freopen("jiben.in","r",stdin);
freopen("jiben.out","w",stdout);
int T,x;
scanf("%d %d",&T,&MO);
Prepare();//先把所有的答案都求出来
for(int tmn=1;tmn<=T;tmn++)
{
scanf("%d",&x);
printf("%d\n",jb[x]);
}
return 0;
}