神奇的珂学组合题——Nephren Runs a Cinema

## 神奇的珂学组合题——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$ 个。  那我们能不能用这种方法表示本题中的合法括号字符串呢？当然也是可以的。如果我们的合法字符串长度为 $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$ 个左括号。  根据一一对应关系，只要我们计算出了合法的路径的条数，也就得到了相应的字符串数。 那么如何计算合法路径条数呢？为方便起见，下面令 $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)$。  我们下面要说明，从 $(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/)是天！ [](https://www.luogu.com.cn/problem/P3933) [奈芙莲（Nephren）](https://nephren.ac.cn/)天下第一！ [](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)也很可爱！（本题中菈琪旭也有出现哦） [](https://img.sukasuka.cn:2333/post/1479)