神奇的珂学组合题——Nephren Runs a Cinema
Sweetlemon
2020-07-27 15:40:30
## 神奇的珂学组合题——Nephren Runs a Cinema
[题目链接](https://www.luogu.com.cn/problem/CF896D)
### 题意
对一个字符串 $S$,定义 $f(S)$ 表示 $S$ 中含有的左括号数与右括号数之差(方便起见,以下使用尖括号 $\mathtt{<}$ 和 $\mathtt{>}$)。如 $f(\mathtt{<>})=0,f(\mathtt{<>>})=-1,f(\mathtt{<oo})=1,f(\mathtt{o})=0$。
定义满足以下条件的字符串 $S$ 为“合法字符串”:
- $S$ 只由左括号 $\mathtt{<}$、右括号 $\mathtt{>}$ 和字符 $\mathtt{o}$ 组成(但三种字符不一定都要出现)。
- 对 $S$ 的任意前缀 $T$(包括 $S$ 本身),都满足 $f(T)\ge 0$,即 $T$ 中左括号数不多于右括号数。
求长度为 $n$ 且 $f(S)\in [l,r]$ 的合法字符串 $S$ 的个数模 $p$ 的值。
$1\le n\le 10^5,\ 0\le l\le r\le n,\ 1\le p\le 2\times 10^9$,不保证 $p$ 是质数。
这个题意翻译中的“左括号”对应原题中携带 100 元钞票的顾客,“右括号”对应携带 50 元钞票的顾客,“$\mathtt{o}$”对应 VIP 顾客,$f(S)$ 对应电影院剩下的 50 元钞票的数目。
### 解法
(提示:如果看不清公式,尝试放大页面)
#### 列出式子
$S$ 中有三种字符,太复杂了,我们可以先进行一个转化。因为字符 $\mathtt{o}$ 对其他影响不大,所以我们可以先从 $n$ 个位置中选出若干个放字符 $\mathtt{o}$,剩下的位置依次放括号。设括号共有 $i$ 个,那么放置字符 $\mathrm{o}$ 的方法就有 $\mathrm{C}^i_n$ 种。经过这一处理,下面我们就不需要管字符 $\mathrm{o}$ 了。
现在需要解决的问题变成,求长为 $i\ (0\le i\le n)$ 的**合法**的括号串(只含括号)$S$ 中,$f(S)\in [l,r]$ 的有多少种。
首先想想我们可以怎么计算 $f$。研究定义,我们发现,$f(S\mathtt{<})=f(S)+1$,$f(S\mathtt{>})=f(S)-1$,当然第二个转化只有当 $f(S)>0$ 时 $S\mathtt{>}$ 才是合法的。
于是,我们可以想到这样一个 dp:设 $g[i][j]$ 表示长度为 $i$ 的字符串中,$f(S)=j$ 的有多少个,这里 $j\ge 0$。根据 $f$ 的计算方法,得到转移方程 $g[i][j]=g[i-1][j-1]+g[i-1][j+1]$,其中的第一项只有 $j\ge 1$ 时才加入。
这个方程是 $\mathrm{O}(n^2)$ 的,并不满足我们的要求。那么,我们可能要转变思路,换一种方法解题。
关于“括号”,你想到了什么呢?如果想到“卡特兰数”,那么你离 AC 就更近了一步。卡特兰数 $C_n$ 表示的是“长为 $n$ 的**合法**的括号串 $S$ 中,$f(S)=0$ 的有多少个”,我们能不能用类似的方法解决上面的问题呢?
~~推倒卡特兰数娘~~ 推导卡特兰数的通项公式时,我们看到了这样一种图形解法:设横坐标 $x$ 表示当前前缀 $T$ 中左括号的个数,纵坐标 $y$ 表示当前前缀 $T$ 中右括号的个数,那么当前前缀对应的坐标点就是 $(x,y)$。根据定义,$f(T)=x-y$,因为要求 $f(T)\ge 0$,因此 $x\ge y$,也就是这些坐标点不能到达直线 $y=x$ 的上方。
下图中的路径 $AGHIJKLMNOPQB$ 表示的是 $\mathtt{<<><>><<>><>}$,这是一个合法括号字符串,且左括号和右括号各有 $6$ 个。
![卡特兰数回顾](https://cdn.luogu.com.cn/upload/image_hosting/7nuyhwwq.png)
那我们能不能用这种方法表示本题中的合法括号字符串呢?当然也是可以的。如果我们的合法字符串长度为 $i$,$f(S)$ 为 $j$,那么这个字符串对应的路径起点就是 $(0,0)$,终点是 $\left(\cfrac{i+j}{2},\cfrac{i-j}{2}\right)$(注意横坐标表示左括号个数,纵坐标表示右括号个数),每次只往右(表示加一个左括号)或往上(表示加一个右括号)走一个单位,并且始终不到达直线 $y=x$ 的上方(也可以说,始终不触及直线 $y=x+1$)。这样的路径和本题中的合法字符串是一一对应的。
例如,下图中的路径 $AGHIJKLMNOP$ 表示的是 $\mathtt{<><<>><<><}$,这个字符串的长度为 $6+4=10$,其中有 $6$ 个右括号和 $4$ 个左括号。
![用图表示合法字符串](https://cdn.luogu.com.cn/upload/image_hosting/sm404867.png)
根据一一对应关系,只要我们计算出了合法的路径的条数,也就得到了相应的字符串数。
那么如何计算合法路径条数呢?为方便起见,下面令 $q$ 表示 $\cfrac{i+j}{2}$,$r$ 表示 $\cfrac{i-j}{2}$,那么我们想要计算的路径的终点就是 $(q,r)$。
如果只需要计数从 $(0,0)$ 到 $(q,r)$ 的(最短)路径条数,这并不太难,只需 $\mathrm{C}_{q+r}^q$ 即可。但合法路径多了一个条件——不能触及直线 $y=x+1$,这该怎么办呢?
我们用这样的思路,用总路径条数 $\mathrm{C}_{q+r}^q$ 减去不合法(触及直线 $y=x+1$)的路径条数,就能得到合法的路径条数。
现在我们要计算不合法的路径条数,这时我们要用推卡特兰数通项时的经典方法——对称。作终点 $T(q,r)$ 关于直线 $l: y=x+1$ 的对称点 $T'(r-1,q+1)$,那么我们会发现,如果把一条不合法路径**第一次触及直线 $l$ 之后的部分**关于 $l$ 作对称,那么这条路径最终将会到达 $T’$ 点(下面会说明为什么)。
如下图所示,$l$ 在下图中被标为红色(“红线”)。图中这条不合法路径的终点是 $P(6,4)$,而对称后的路径终点是 $P'(4-1,6+1)=P'(3,7)$。
![将不合法路径对称](https://cdn.luogu.com.cn/upload/image_hosting/dol9geig.png)
我们下面要说明,从 $(0,0)$ 到 $(q,r)$ 的**不合法路径**与从 $(0,0)$ 到 $(r-1,q+1)$ 的**路径**一一对应。
首先说明,根据任意一条从 $(0,0)$ 到 $(q,r)$ 的不合法路径,都恰能构造一条从 $(0,0)$ 到 $(r-1,q+1)$ 的路径。任意一条不合法路径都一定会触及到直线 $l:y=x+1$,找到第一次触及的位置(设为 $(t,t+1)$),那么原路径在此后还要向右走 $q-t$ 步,向上走 $r-t-1$ 步,也就是今后的总位移是 $(q-t,r-t-1)$。现在将原路径对称,也就是原先向右的步改成向上,原先向上的改成向右,那么新路径此后的位移就将是 $(r-t-1,q-t)$,于是终点就是 $(t+r-t-1,t+1+q-t)$,即为 $(r-1,q+1)$。而且两条不同的不合法路径,所对称出来的路径也是不同的。
再说明,根据任意一条从 $(0,0)$ 到 $(r-1,q+1)$ 的路径,都恰能(逆向)构造一条从 $(0,0)$ 到 $(q,r)$ 的不合法路径。由于 $(r-1,q+1)$ 在 $y=x+1$ 的上方(证明从略,可看图),并且起点 $(0,0)$ 在 $l$ 的下方,因此从 $(0,0)$ 到 $(r-1,q+1)$ 的路径一定会跨越直线 $l$。取路径与 $l$ 的交点,在交点后像上面一样作对称,仿照上面的过程,我们可以知道对称后路径会到达 $(q,r)$。由于触及了直线 $l$,因此这样构造出来的路径是不合法的。两条不同的从 $(0,0)$ 到 $(r-1,q+1)$ 的路径,所对称出来的不合法路径也是不同的。
综上,从 $(0,0)$ 到 $(q,r)$ 的不合法路径与从 $(0,0)$ 到 $(r-1,q+1)$ 的路径一一对应;因此,从 $(0,0)$ 到 $(q,r)$ 的不合法路径数就等于从 $(0,0)$ 到 $(r-1,q+1)$ 的路径,也就是 $\mathrm{C}^{q+1}_{r-1+q+1}=\mathrm{C}_{q+r}^{q+1}$。
综合前面的结果,我们得出,长度为 $i$,$f(S)$ 为 $j$ 的合法字符串 $S$ 的个数是 $\mathrm{C}_{q+r}^{q}-\mathrm{C}_{q+r}^{q+1}=\mathrm{C}_{i}^{\frac{i+j}{2}}-\mathrm{C}_{i}^{\frac{i+j+2}{2}}$。
#### 化简式子
得出了上面的式子,我们要计算的也就是
$$
\sum_{i=0}^{n}\mathrm{C}_{n}^{i}\left(\sum_{j=l}^{r}\mathrm{C}_{i}^{\frac{i+j}{2}}-\mathrm{C}^{\frac{i+j+2}{2}}_i\right)
$$
注意,为了写式子和计算方便,当 $r>n$ 时,我们定义 $\mathrm{C}_{n}^r=0$。另外,如果你想不起来 $\mathrm{C}_n^i$ 是什么,回忆我们对 $\mathtt{o}$ 字符的处理过程。
这个式子直接计算是 $\mathrm{O}(n^2)$ 的,我们能不能化简呢?
首先搞清楚一个问题:上式的组合数中出现了 $\frac{i+j}{2}$ 这样的部分,那万一这是个分数呢?联系问题的意义,$i$ 是括号总数,$j$ 是左括号与右括号数之差,而 $\frac{i+j}{2}$ 表示了左括号的数量,必须要是整数。因此上式还有一个隐含条件,即 $i,j$ 的奇偶性相同。
接下来可以上手化简了。先别急着把组合数按定义展开,如果搞懂了上面的问题,事实上,上式中大圆括号包裹的求和号可以直接化简!为什么呢?我们注意到 $\mathrm{C}_i^{\frac{i+j}{2}}$ 和 $\mathrm{C}_i^{\frac{i+j+2}{2}}$ 有密切的关系,为了方便讨论,我们令 $b_{j} =\mathrm{C}_{i}^{\frac{i+j}{2}}$,那么这个求和可以表示为 $\sum_{j=l}^{r}b_j-b_{j+2}$。如果还没有看出来,把它展开,注意 $i,j$ 的奇偶性相同。设第一个使式子有意义的 $j$ 是 $j_0$,最后一个使式子有意义的 $j$ 是 $j_1$,那么这个求和式就是 $b_{j_0}-b_{j_0+2}+b_{j_0+2}-b_{j_0+4}+\cdots + b_{j_{1}}-b_{j_{1}+2}$。仔细看,相邻项消掉了,只剩下 $b_{j_0}-b_{j_1+2}$,也就是 $\mathrm{C}_i^{\frac{i+j_{0}}{2}}-\mathrm{C}_i^{\frac{i+j_{1}+2}{2}}$。
这样,我们的式子就变成了
$$
\sum_{i=0}^{n}\mathrm{C}_{n}^{i}\left(\mathrm{C}_{i}^{\frac{i+j_0}{2}}-\mathrm{C}^{\frac{i+j_1+2}{2}}_i\right)
$$
从而可以在 $\mathrm{O}(n)$ 级别完成计算。
$j_0$ 和 $j_1$ 是多少呢?我们看看 $j$ 需要满足的限制条件。$j\ge 0$ 是题目要求的,$j\le i$ 是实际意义要求的(回忆 $j=f(S)$ 和 $f$ 的定义),$l\le j\le r$ 也是题目要求的,同时 $i,j$ 的奇偶性相同。从而,$l\le j\le \min(i,r)$,并且确定上下界后还要将 $j$ 加 $1$ 或减 $1$(上界减 $1$,下界加 $1$),以保证 $i,j$ 的奇偶性相同。
#### 程序设计
问题还没有解决完,组合数怎么算?
这里 $1\le p\le 2\times 10^9$,并且不保证是质数,这让我们计算阶乘逆元有了困难。其实,我们可以用一种类似“扩域”的思想处理。
首先特判 $p=1$ 的情形,如果 $p=1$ 直接输出 $0$,完全不用计算。
接下来将 $p$ 分解质因数,分解成 $p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\cdots p_k^{\alpha_k}$ 的形式。$p$ 至多有 $9$ 个不同质因子(这是因为 $2\times 3\times 5\times 7\times 11\times 13\times 17\times 19\times 23\times 29>2\times 10^9$)。
在计算阶乘和阶乘的逆元时,我们把每个数表示成 $x\cdot p_1^{\beta_1}p_2^{\beta_2}p_3^{\beta_3}\cdots p_k^{\beta_k}$ 的形式,其中 $x$ 与 $p$ 互质。这样,两个数相乘,就让它们的 $x$ 相乘并模 $p$,指数相加;两个数相除,就让它们的 $x$ 相除(就是乘逆元)并模 $p$,指数相减。
可是这个结构怎么支持加减法呢?事实上,不需要支持加减法!我们使用这样的结构的原因,是我们想要处理**除法**。如果处理的是加、减、乘,那不管操作数是否与 $p$ 互质,都可以像我们熟悉的那样操作。而整个计算过程中,只有组合数的计算需要用到除法,因此我们计算完组合数之后,就可以把结果的 $x\cdot p_1^{\beta_1}p_2^{\beta_2}p_3^{\beta_3}\cdots p_k^{\beta_k}$ 模 $p$,按照正常的方式进行下面的计算。
因为要使用这样的结构,整个计算过程将是 $\mathrm{O}(n\log n)$ 的。
另外,还要额外注意,因为 $p\le 2\times 10^9$,因此不像平常我们写的那样,在这里两个模 $p$ 后的数相加仍会超出 `signed int` 的范围。在这里推荐一下 Codeforces 的提示功能,在平时练习交题时,它可能会提示如整数溢出、数组越界这样的问题,像这个整数越界它就会提示 Probably, the solution is executed with error 'signed integer overflow' on the line xx。真是感谢 Codeforces 节约了我的时间!~~另外,洛谷啥时候整个这样的功能啊?~~
#### 做题总结
这是一道很有价值的题目,至少有三个点可以积累。
- 列出式子方面,积累卡特兰数的经典处理方法。
- 化简式子方面,强化“注意相同的结构”的思想。
- 程序设计方面,模任意模数的组合数处理方法。
#### 代码参考
```cpp
#include <cstdio>
#include <cctype>
#include <algorithm>
#define MAXIOLG 25
#define FILENAME(x)\
freopen(x".in","r",stdin);\
freopen(x".out","w",stdout);
#define LOWBIT(x) ((x)&(-(x)))
#define MD(x) (((x)>=(p))?((x)-=(p)):(0))
#define MAXPR 10
#define MAXN 100005
using namespace std;
typedef long double ld;
typedef long long ll;
typedef ll io_t;
io_t shin[MAXIOLG];
io_t seto(void); //快速读入
void ayano(io_t x,char spliter='\n'); //快速输出
int p,phip,phipm; //p, p 的欧拉函数,p 的欧拉函数减 1(用于计算逆元)
int prims[MAXPR],primdeg[MAXPR],primcnt=0; //分解质因数的结果
int kasumi(int a,int b); //快速幂
int comb(int a,int b); //组合数
struct Num{
int x,xinv,degs[MAXPR]; //互质部分, 互质部分的逆元, 指数部分
Num(void):x(1),xinv(1){ //构造函数
for (int i=1;i<=primcnt;i++)
this->degs[i]=0;
}
Num(int y){ //从一个整数构造
for (int i=1;i<=primcnt;i++){
int ip=prims[i];
int d=y/ip;
this->degs[i]=0;
while (d*ip==y)
this->degs[i]++,y=d,d=y/ip;
}
y%=p;
this->x=y,this->xinv=kasumi(y,phipm);
}
Num(const Num& tn):x(tn.x),xinv(tn.xinv){ //“复制构造”
for (int i=1;i<=primcnt;i++)
this->degs[i]=tn.degs[i];
}
int output(void){ //转换为普通数
int oans=this->x;
for (int i=1;i<=primcnt;i++)
oans=1ll*oans*kasumi(prims[i],this->degs[i])%p;
return oans;
}
friend Num operator*(const Num& lhs,const Num& rhs); //相除
friend Num operator/(const Num& lhs,const Num& rhs); //相乘
};
Num factors[MAXN]; //预处理阶乘
int main(void){
int n,l,r;
n=seto(),p=seto(),l=seto(),r=seto();
if (p==1){ //特判
ayano(0);
return 0;
}
int tp=p; //分解质因数,注意不要在原来的数上分解
phip=p; //同时计算 phi 值
for (int ip=2;ip*ip<=tp;ip++){
int d=tp/ip;
if (!(d*ip==tp))
continue;
primcnt++,prims[primcnt]=ip,phip=phip/ip*(ip-1);
while (d*ip==tp)
primdeg[primcnt]++,tp=d,d=tp/ip;
}
if (tp>1) //大于 sqrt(p) 的质因子
primcnt++,prims[primcnt]=tp,primdeg[primcnt]=1,phip=phip/tp*(tp-1);
phipm=phip-1;
factors[0]=Num(1); //预处理阶乘
for (int i=1;i<=n;i++)
factors[i]=Num(i)*factors[i-1];
ll ans=0;
for (int i=l;i<=n;i++){
int lb=l;
((lb^i)&1)?(lb++):(0); // i,j 奇偶性一致
int rb=min(i,r);
((rb^i)&1)?(rb--):(0); // i,j 奇偶性一致
if (lb>rb)
continue;
ll tans=1ll*comb(i,(i+lb)/2)+p-comb(i,(i+rb+2)/2); //这个地方记得用 long long,否则加法溢出
MD(tans);
tans=1ll*tans*comb(n,i)%p;
ans+=tans,MD(ans);
}
ayano(ans);
return 0;
}
//计算组合数
int comb(int a,int b){
//C_a^b
if (b>a)
return 0;
Num cansn=factors[a]/factors[b];
cansn=cansn/factors[a-b];
return cansn.output(); //转换为普通的数
}
//快速幂
int kasumi(int a,int b){
int kans=1;
while (b)
(b&1)?(kans=1ll*kans*a%p):(0),
b>>=1,a=1ll*a*a%p;
return kans;
}
//两个数的相乘,互质部分相乘,指数相减
Num operator*(const Num& lhs,const Num& rhs){
Num mans(lhs);
mans.x=1ll*mans.x*rhs.x%p;
mans.xinv=1ll*mans.xinv*rhs.xinv%p;
for (int i=1;i<=primcnt;i++)
mans.degs[i]+=rhs.degs[i];
return mans;
}
//两个数的相除,乘逆元,指数相减
Num operator/(const Num& lhs,const Num& rhs){
Num mans(lhs);
mans.x=1ll*mans.x*rhs.xinv%p;
mans.xinv=1ll*mans.xinv*rhs.x%p;
for (int i=1;i<=primcnt;i++)
mans.degs[i]-=rhs.degs[i];
return mans;
}
//快速读入
io_t seto(void){
io_t seto_x=0;
int symbol=0;
char ch=getchar();
while (!isdigit(ch))
(ch=='-')?(symbol=1):(0),ch=getchar();
while (isdigit(ch))
(seto_x=seto_x*10+(ch-'0')),ch=getchar();
return (symbol)?(-seto_x):(seto_x);
}
//快速输出
void ayano(io_t ayano_x,char spliter){
if (!ayano_x){
putchar('0'),putchar(spliter);
return;
}
if (ayano_x<0)
putchar('-'),ayano_x=-ayano_x;
int ayano_len=0;
while (ayano_x){
io_t ayano_d=ayano_x/10;
shin[ayano_len++]=ayano_x-ayano_d*10;
ayano_x=ayano_d;
}
while (ayano_len--)
putchar(shin[ayano_len]+'0');
putchar(spliter);
}
```
#### 珂学宣传
[珂朵莉(Chtholly)](https://www.chtholly.ac.cn/)是天!
[![Chtholly](https://cdn.luogu.com.cn/upload/pic/9235.png)](https://www.luogu.com.cn/problem/P3933)
[奈芙莲(Nephren)](https://nephren.ac.cn/)天下第一!
[![Nephren](https://cdn.luogu.com.cn/upload/pic/9263.png)](https://www.luogu.com.cn/problem/P4691)
[菈琪旭(Lakhesh)](https://wiki.sukasuka.cn/%E8%8F%88%E7%90%AA%E6%97%AD%C2%B7%E5%B0%BC%E5%85%8B%E6%96%AF%C2%B7%E7%91%9F%E5%B0%BC%E6%AC%A7%E9%87%8C%E6%96%AF)也很可爱!(本题中菈琪旭也有出现哦)
[![Lakhesh](https://cdn.luogu.com.cn/upload/image_hosting/i3gotdn1.png)](https://img.sukasuka.cn:2333/post/1479)