YbtOJ 784「莫队算法」序列计数

(Updated: )
oi
,

题目链接：YbtOJ #784

小 A 正在研究单调上升序列。

他打算进行若干组询问，每次给定三个整数 $l,r,x$，希望求出有多少个序列 $A$ 满足：

  • 序列的长度 $m$ 是 $l\sim r$ 中的一个整数。
  • $1\le A_1 < A_2 < A_3 < \cdots < A_m \le x$。

你只需要输出答案向 $998244353$ 取模的结果。

$T\le 2\times10^5$，$1\le l\le r\le x\le 2\times10^5$。

Solution

记 $S(n,m)=\sum_{i=0}^mC_n^i$，则题目中要求的就是 $\sum_{i=l}^rC_x^i=S(n,r)-S(n,l-1)$。

于是题意转化为给定 $2T$ 组 $x,y$，询问 $S(x,y)$ 的值。

然后发现这东西实际上可以用莫队做：

  • $y$ 加 $1$：直接加上 $C_x^{y+1}$。
  • $y$ 减 $1$：直接减去 $C_x^y$。
  • $x$ 加 $1$：考虑 $S(x+1,y)=C_{x+1}^0+\sum_{i=1}^yC_{x+1}^i=C_x^0+\sum_{i=1}^y(C_x^i+C_x^{i-1})=2S(x,y)-C_x^y$。
  • $x$ 减 $1$：将上面的式子变个形，就得到 $S(x-1,y)=\frac{S(x,y)+C_{x-1}^y}2$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
    Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
    Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=4e5+10,p=998244353,Inv2=(p+1)/2;
int n,S,bl[N],fac[N],ifac[N],l,r,cnt;LL ans[N],Ans;
struct node{int l,r,id;}q[N];
struct Que{int l,r,x,id;}Q[N];
I int C(CI n,CI m){return 1LL*fac[n]*ifac[m]%p*ifac[n-m]%p;}
I int QP(RI a,RI b){RI s=1;W(b) b&1&&(s=1LL*s*a%p),a=1LL*a*a%p,b>>=1;return s;}
I bool cmp(Cn node& x,Cn node& y){return bl[x.l]^bl[y.l]?x.l<y.l:bl[x.l]&1?x.r<y.r:x.r>y.r;}
I void add(LL& x,CI y){(x+=y)>=p&&(x-=p);}
int main(){
    RI i;for(read(n),i=1;i<=n;i++) read(Q[i].l,Q[i].r,Q[i].x),q[++cnt]=(node){Q[i].x,Q[i].r,i},q[++cnt]=(node){Q[i].x,Q[i].l-1,-i};
    for(S=sqrt(cnt),i=1;i<=cnt;i++) bl[i]=(i-1)/S+1;for(fac[0]=1,i=1;i<N;i++) fac[i]=1LL*fac[i-1]*i%p;for(ifac[N-1]=QP(fac[N-1],p-2),i=N-2;~i;i--) ifac[i]=1LL*ifac[i+1]*(i+1)%p;
    #define abs(x) ((x)<0?-(x):(x))
    for(sort(q+1,q+cnt+1,cmp),Ans=l=1,r=0,i=1;i<=cnt;i++){
        W(l<q[i].l) Ans=(2LL*Ans%p-C(l,r)+p)%p,l++;W(r>q[i].r) add(Ans,p-C(l,r)),r--;
        W(l>q[i].l) Ans=(1LL*Inv2*(Ans+C(l-1,r))%p)%p,l--;W(r<q[i].r) add(Ans,C(l,r+1)),r++;
        add(ans[abs(q[i].id)],q[i].id<0?p-Ans:Ans);
    }for(i=1;i<=n;i++) writeln((ans[i]+p)%p);return cerr<<clock()<<'\n',clear(),0;
}