YbtOJ 784「莫队算法」序列计数
题目链接：YbtOJ #784
小 A 正在研究单调上升序列。
他打算进行若干组询问，每次给定三个整数 l,r,x，希望求出有多少个序列 A 满足：
- 序列的长度 m 是 lsim r 中的一个整数。
- 1le A_1 < A_2 < A_3 < cdots < A_m le x
你只需要输出答案向 998244353 取模的结果。
Tle 2times10^5，1le lle rle xle 2times10^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
代码语言：javascript复制#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 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;
}
