AT_abc463_g 题解

· · 题解

非常巧妙。

个人认为很有趣的一个题喵。

先让 X \gets |X|，然后因为它还关于原点对称，所以只需要考虑 [0,X] 这一段，然后让答案 \times 2 即可。

首先我们要注意到的一个点，就是如果你走的时候一直没有超过 X，那么最终你走到的点的期望位置就是 0，因为往左往右概率是一样的。这个可以自己推一下。

那么等价于就是说，如果某个询问 n < X 则实际上答案就是 X。这个从样例的第四组输入也能看得出来。

那么排除掉前面 \le X 的部分，推式子可以得到答案 \frac{1}{2^{n-1}} \sum_{i=X+1}^{n} [i \equiv n \bmod 2]i \binom{n}{\frac{n-i}{2}}。

但是这还有对奇偶性的限制以及后面的除法部分，未免太难受了，令 j = \frac{n-i}{2}，那么可以得到更舒服的式子 \frac{1}{2^{n-1}} \sum_{j=0}^{\lfloor \frac{n-X-1 }{2}\rfloor} \rfloor (n-2j) \binom{n}{j}，再拆开 \frac{1}{2^{n-1}} \left ( \sum_{j=0}^{\lfloor \frac{n-X-1 }{2}\rfloor} n \binom{n}{j} - \sum_{j=0}^{\lfloor \frac{n-X-1 }{2}\rfloor} 2 j \binom{n}{j} \right )。

那么对于一组 (n,X) 的询问，其实可以化作对于 (n,m) 求 \frac{1}{2^{n-1}} \left ( n \sum_{j=0}^{m} \binom{n}{j} - 2 \sum_{j=0}^{m} j \binom{n}{j} \right )（其中 m = \lfloor \frac{n-X-1 }{2}\rfloor），而需要重点维护的就是 \sum_{j=0}^{m} \binom{n}{j} 和 \sum_{j=0}^{m} j \binom{n}{j}。

这个东西暴力做肯定是不行的，但我们可以考虑莫队。不会？请左转莫队模板学习。这里考虑的是一个前缀 [0,m]，因此只要维护右端点。然后同步用两个变量 ans 和 ansk 记录 \sum_{j=0}^{m} \binom{n}{j} 和 \sum_{j=0}^{m} j \binom{n}{j} 当前的值。

但是不同查询的 n 是不一样的，所以在莫队的过程中，会遇到类似 \sum_{j=0}^{m} \binom{n}{j} 变为 \sum_{j=0}^{m} \binom{n+1}{j} 的情况。此时显然不能再全部重新算一遍啊，有什么快速的方法吗？

发现这个 n 的增长、减少很像帕斯卡公式 \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} 的形式啊，那不妨把帕斯卡公式代进去试试。

然后你就会得到两坨式子，虽然不好看，但是能 O(1) 变化。

可以发现加和减的变化是相反的，因此理解了一边也一定能理解另一边。如果你实在推不出为何，可以从最终式子代入数值反推回原始式子。但不管你是怎么推的，一定一定要记得在必要时用上帕斯卡公式！！

那么就做完了，套一个莫队的板子即可。顺便推销我的莫队模板题题解。

取模时如果出现减法一定要加上模数再取模啊！！

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
const int up = 200000;
const LL MOD = 998244353;
struct query{LL n,m,x,d,id;}q[N];
LL Q,sq,ans[N];
LL fac[N],inv[N],inv2;
LL nown,nowm,Ansk,Ans=1;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
LL QP(LL x,LL y=MOD-2){
    LL as=1;
    while(y){
        if(y&1)as=as*x%MOD;
        x=x*x%MOD,y>>=1;
    }return as;
}
void init_(){
    fac[0]=1,inv[0]=1;inv2=QP(2);
    for(LL i=1;i<=up;i++)
        fac[i]=fac[i-1]*i%MOD;
    inv[up]=QP(fac[up]);
    for(LL i=up-1;i>=1;i--)
        inv[i]=inv[i+1]*(i+1)%MOD;
    return;
}
bool cmp(query q1,query q2){
    if(q1.n/sq!=q2.n/sq)return q1.n<q2.n;
    if((q1.n/sq)&1)return q1.m<q2.m;
    else return q1.m>q2.m;
}
LL C(LL x,LL y){
    if(x<0||y<0||x<y)return 0;
    LL res=fac[x]*inv[x-y]%MOD;
    return res*inv[y]%MOD;
}
void addN(){
    Ansk=((2*Ansk+Ans)%MOD-(nowm+1)*C(nown,nowm)%MOD+MOD)%MOD;
    Ans=(2*Ans%MOD-C(nown,nowm)+MOD)%MOD;
    return;
}
void delN(){
    Ans=(Ans+C(nown-1,nowm))%MOD*inv2%MOD;
    Ansk=(Ansk-Ans+MOD+(nowm+1)*C(nown-1,nowm)%MOD)%MOD*inv2%MOD;
    return;
}
void addM(){
    Ans=(Ans+C(nown,nowm+1))%MOD;
    Ansk=(Ansk+(nowm+1)*C(nown,nowm+1)%MOD)%MOD;
    return;
}
void delM(){
    Ans=(Ans-C(nown,nowm)+MOD)%MOD;
    Ansk=(Ansk-nowm*C(nown,nowm)%MOD+MOD)%MOD;
    return;
}
int main(){
    Q=read(),sq=sqrt(up);init_();
    for(int i=1;i<=Q;i++){
        q[i].n=read(),q[i].x=abs(read());
        q[i].d=q[i].n-q[i].x,q[i].m=(q[i].d-1)/2;
        q[i].id=i;
    }sort(q+1,q+Q+1,cmp);
    for(int i=1;i<=Q;i++){
        if(q[i].x>=q[i].n){
            ans[q[i].id]=q[i].x%MOD;
            continue;
        }
        while(nown<q[i].n)addN(),nown++;
        while(nown>q[i].n)delN(),nown--;
        while(nowm<q[i].m)addM(),nowm++;
        while(nowm>q[i].m)delM(),nowm--;
        LL res=QP(inv2,q[i].n-1)*(q[i].d*Ans%MOD-2*Ansk%MOD+MOD)%MOD;
        ans[q[i].id]=(q[i].x+res)%MOD;
    }
    for(int i=1;i<=Q;i++)cout<<ans[i]<<"\n";
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！