Sweetlemon 的博客

Sweetlemon 的博客

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

posted on 2020-07-27 15:40:30 | under 题解 |

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

题目链接

题意

对一个字符串 $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 节约了我的时间!另外,洛谷啥时候整个这样的功能啊?

做题总结

这是一道很有价值的题目,至少有三个点可以积累。

  • 列出式子方面,积累卡特兰数的经典处理方法。
  • 化简式子方面,强化“注意相同的结构”的思想。
  • 程序设计方面,模任意模数的组合数处理方法。

代码参考

#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)是天!

Chtholly

奈芙莲(Nephren)天下第一!

Nephren

菈琪旭(Lakhesh)也很可爱!(本题中菈琪旭也有出现哦)

Lakhesh