CF896D Nephren Runs a Cinema 题解

· · 题解

和其他题解不太一样的柿子。

把 0 元，50 元，100 元分别看成 -1，0，1，则问题转化成有多少种由 -1，0，1，构成的长为 n 的序列满足：

由前一个条件可以想到卡特兰数。如果已经确定要用 n 个 1，m 个 -1，构成满足第一个条件的序列，则由卡特兰数得答案为 \binom{n+m}{n} - \binom{n+m}{n+1}。

于是想到先枚举 1 的个数，再枚举 -1 的个数。令 1 的个数为 i，-1 的个数为 j，容易得到符合条件的 j 的区间 [l,r]。然后还要把这 i+j 个数放进序列里，方案为 \binom{n}{i+j}。

于是就有柿子：

\sum_{j=l}^{r}{\binom{n}{i+j}\cdot\left(\binom{i+j}{i}-\binom{i+j}{i+1} \right)}

这个柿子括号里外都有 i+j 不太好化简的样子。不如先把它拆开，为：

\sum_{j=l}^{r}{\binom{n}{i+j}\cdot\binom{i+j}{i}}-\sum_{j=l}^{r}{\binom{n}{i+j}\cdot\binom{i+j}{i+1}}

先看前面那部分，组合意义：先从 n 个里选 i+j 个，再从中选 i 个。不妨改变顺序，先从 n 个里选 i 个，再从剩下 n-i 个里选 j 个，于是就变成了：

\binom{n}{i}\cdot\sum_{j=l}^{r}{\binom{n-i}{j}}

发现后面是组合数单行区间和的形式，等会可以解决。后半部分同理，下面有式子。

令 l_j,r_j 为一个 i 对应 j 的区间左右端点，总的柿子就变成了：

\sum_{i=L}^{n}{\left(\binom{n}{i}\cdot\sum_{j=l_i}^{r_i}{\binom{n-i}{j}}-\binom{n}{i+1}\cdot\sum_{j=l_i}^{r_i}{\binom{n-i-1}{j-1}}\right)}

再来说那个组合数单行区间和。首先可以拆成前缀和相减，现在来讨论前缀和。设第 n 行前 m 列求和为 S(n,m)。

试着把每个 S 都写出来可以发现 S(n,m)=S(n-1,m-1)+S(n-1,m)，与组合数递推式相同。把 S(n,m) 的每个组合数都拆到上一行即可证明。

所以可以用一个指针记录某一位置的 S(n,m)，再来讨论指针的移动。

为了方便，S(n,m) 记为 y，指针再记录一个 S(n-1,m-1) 记为 x。

左右移动就直接计算单点组合数就可以做到。

下移：y 左移一位即可得到新的 x，再由新的 x 与旧的 y 加和，由上面的递推式得，即为新的 y。

上移：x 右移一位得到新的 y。如果现在要由 S(n,m) 得到 S(n-1,m)，可以知道：

S(n,m)=S(n-1,m-1)+S(n-1,m)=2\cdot S(n-1,m) -\binom{n-1}{m}

所以 S(n-1,m)=\frac{S(n,m)+\binom{n-1}{m}}{2}。

要拿来减的左右前缀和分两个指针的话，可以发现每次要求的 S(n,m) 位置相近，直接暴力移指针即可。

然后这题又是个任意模数···把模数质因数分解成 \prod{p_i^{c_i}}，然后把每个数分成与模数互质的部分，用 {p_i^{c`_i}} 来表示不互质的部分。互质的存在逆元，扩展欧几里得可以求，不互质的已经分解，乘除法容易定义，化成普通的形式可以加减。预处理出竭诚，组合数就可以求了。

···但是还有个问题，注意到 S(n,m) 的指针上移同时需要加法和除法，2 可能不存在逆元，要套用上面方法的话加法并不好定义，那怎么办呢？

···那就避免上移就好了。逆序枚举 i，总式子先算右边，就可以让指针单调不升了。上☆键☆已☆扣。

优雅的代码不会 #define int long long。码喵：

#include<bits/stdc++.h>
#define EL puts("Elaina")
#define reg register int
typedef long long ll;
using namespace std;
const int maxn=1e5+3,maxp=11;
int n,mod,L,R,cnt,p[maxp];
inline int qpow(int a,int b){
    assert(b>=0);
    int ans=1;
    for(;b;b>>=1,a=1ll*a*a%mod)
        if(b&1)ans=1ll*ans*a%mod;
    return ans;
}
inline void exgcd(int a,int b,ll &x,ll &y){
    if(!b){x=1,y=0;return;}
    exgcd(b,a%b,y,x),y-=a/b*x;
}
inline int inv(int a){
    ll x,y;exgcd(a,mod,x,y);
    return (x+mod)%mod;
}
inline void init(){
    int res=mod;
    for(reg i=2;i*i<=mod;++i)
        if(res%i==0){
            p[++cnt]=i;
            while(res%i==0)res/=i;
        }
    if(res^1)p[++cnt]=res;
}
struct number{
    int c[maxp];
    number(){}
    number(ll x){
        memset(c,0,sizeof(c));
        for(reg i=1;i<=cnt;++i)
            while(x%p[i]==0)c[i]++,x/=p[i];
        c[0]=x;
    }
    inline int calc()const{
        int ans=c[0];
        for(reg i=1;i<=cnt;++i)if(c[i])
            ans=1ll*ans*qpow(p[i],c[i])%mod;
        return ans;
    }
    inline void operator *=(const number &a){
        c[0]=1ll*c[0]*a.c[0]%mod;
        for(reg i=1;i<=cnt;++i)c[i]+=a.c[i];
    }
    inline number operator *(const number &a)const{
        number ans=*this;ans*=a;return ans;
    }
    inline void operator /=(const number &a){
        c[0]=1ll*c[0]*inv(a.c[0])%mod;
        for(reg i=1;i<=cnt;++i)c[i]-=a.c[i];
    }
    inline number operator /(const number &a)const{
        number ans=*this;ans/=a;return ans;
    }
}fac[maxn];
inline int C(int n,int m){
    if(m>n)return 0;if(m==0||n==m)return 1;
    return (fac[n]/fac[m]/fac[n-m]).calc();
}
struct CombinationPointer{
    int n,m,x,y;
    CombinationPointer(){n=m=1,x=1,y=2;}
    inline void left(){
        x=(1ll*x+mod-C(n-1,m-1))%mod;
        y=(1ll*y+mod-C(n,m))%mod,--m;
    }
    inline void right(){
        x=(1ll*x+C(n-1,m))%mod;
        y=(1ll*y+C(n,m+1))%mod,++m;
    }
    inline void down(){
        x=(1ll*y+mod-C(n,m))%mod;
        y=(1ll*x+y)%mod,++n;
    }
    inline int query(int tx,int ty){
        if(ty<0)return 0;
        if(!tx)return 1;
        if(!ty)return 1;
        while(m>ty)left();
        while(n<tx)down();
        while(m<ty)right();
        return y;
    }
}p1,p2;
inline void MyDearMoments(){
    scanf("%d%d%d%d",&n,&mod,&L,&R),init();
    fac[0]=fac[1]=number(1);
    for(reg i=2;i<=n;++i)fac[i]=fac[i-1]*number(i);
    int ans=0;
    for(reg i=n;i>=L;--i){
        if(i==n){if(i>=L&&i<=R)ans=(ans+1)%mod;continue;}
        int l=max(i-R,0),r=min(n-i,i-L);
        if(l>r)continue;
        if(!l)ans=(1ll*ans+C(n,i))%mod,++l;
        if(l>r)continue;
        ll res2=((1ll*p1.query(n-i-1,r-1)+mod-p2.query(n-i-1,l-2))%mod)%mod;
        ll res1=((1ll*p1.query(n-i,r)+mod-p2.query(n-i,l-1))%mod)%mod;
        res1=1ll*C(n,i)*res1%mod,res2=1ll*C(n,i+1)*res2%mod;
        ans=((1ll*ans+res1)%mod+mod-res2)%mod;
    }
    printf("%d\n",ans);
}
int main(){return MyDearMoments(),0;}