1 条题解

  • 0
    @ 2025-8-24 22:29:56

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar tommy0221
    别担心，离开只是因为我在重拾快乐

    搬运于2025-08-24 22:29:56，当前版本为作者最后更新于2021-03-08 20:29:41，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    出题人题解。

    为了方便把 VV 加 22。

    一个节点 [l,r][l,r] 能 Pushdown\mathrm{Pushdown} 当且仅当所有覆盖它的修改加起来不等于 00 。

    一次操作它被覆盖的期望为 p=l×(n−r+1)n(n+1)2p=\dfrac{l\times(n-r+1)}{\frac{n(n+1)}{2}} 。

    设覆盖 kk 次，加起来为 00 的方案数为 f(k)f(k) 。

    f(k)=[x0](x−1+1+x+x2+⋯+xV−2)kf(k)=[x^0](x^{-1}+1+x+x^2+\cdots+x^{V-2})^k

    一个节点对于答案的贡献就是

    $$S=\sum_{i=0}^{m}p^i(1-p)^{m-i}\binom{m}{i}\dfrac{V^i-f(i)}{V^i} $$

    把 p1−p\dfrac{p}{1-p} 看做参数，可以得到一个多项式。

    发现总共只有 n−1n-1 个点（线段树非叶节点个数），多点求值就好了，非常简便。

    当然也可以不用这个科技，验题人给了个常数较小的分治FFT做法，稍微推推式子就好了。

    现在唯一剩下的问题是计算 k∈[0,m]k\in [0,m] 的 f(k)f(k) 。

    方法一

    f(k)=[xk](1+x+x2+x3+⋯+xV−1)kf(k)=[x^k](1+x+x^2+x^3+\cdots+x^{V-1})^k =[xk](1−xV1−x)k=[x^k](\frac{1-x^{V}}{1-x})^k (1−xV)k=∑i=0(ki)xiV(−1)i(1-x^V)^k=\sum_{i=0}\binom{k}{i}x^{iV}(-1)^i (1−x)−k=∑i=0(k+i−1i)xi(1-x)^{-k}=\sum_{i=0}\binom{k+i-1}{i}x^{i} $$f(k)=\sum_{i=0}^{\frac{k}{V}}\binom{k}{i}(-1)^i\binom{2k-Vi-1}{k-1} $$

    复杂度 O(m2V)O(\dfrac{m^2}{V}) 。

    方法二

    设

    F(x)=1+x+x2+⋯+xV−1F(x)=1+x+x^2+\cdots+x^{V-1} G(x)=xF(x)G(x)=\dfrac{x}{F(x)}

    我们要求的是 [x0](F(x)x)k[x^0]\left(\dfrac{F(x)}{x}\right)^k，即 [x0]G−k(x)[x^0]G^{-k}(x)。

    可以发现 G(x)G(x) 没有常数项且一次项系数不为 00 。令 G(x)G(x) 的复合逆为 H(x)H(x) 。

    根据EI鸽鸽在员交课件里的《另类拉格朗日反演》一节里的一个式子（感谢 EI 的指导。证明可以看验题人题解，大概是普通拉反证明第一步两边 kk 次幂）：

    若 G,HG,H 互为复合逆，那么

    [xn]Gk=[x−k−1]H′H−n−1[x^n]G^k=[x^{-k-1}]H'H^{-n-1}

    带进去就得到

    [x0]G−k(x)=[xk]H′(x)H(x)x[x^0]G^{-k}(x)=[x^k]\dfrac{H'(x)}{\frac{H(x)}{x}}

    只要算出 H(x)H(x) 就好了。

    注意到

    G(x)=xF(x)=x−x21−xVG(x)=\dfrac{x}{F(x)}=\dfrac{x-x^2}{1-x^V}

    相当于要求一个 H(x)H(x) 满足

    H(x)−H2(x)1−HV(x)≡x\dfrac{H(x)-H^2(x)}{1-H^{V}(x)}\equiv x

    化简一下：

    H(x)−H2(x)−x+xHV(x)≡0H(x)-H^2(x)-x+xH^V(x)\equiv 0

    牛顿迭代即可，复杂度 O(nlog⁡n)O(n\log n) （n,mn,m 视为同阶）。

    综上，使用方法二，复杂度为 O(nlog⁡2n)O(n\log^2 n) 。

    思维难度应该不是很大，有点板子，放 E 应该差不多吧。

    upd：上面那句话是赛前写的，不想删掉/wq。但是原本确实是为了放一个简单一点的 E 才选了这题的，没想到场上最高 3030。。。

    所有点的时限至少为验题人代码 3 倍，std 2 倍多，并且我的板子不算很快，还有极大的优化空间，我用我写过最慢的板子都能过，所以应该不会有人被卡常了。

    #include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define sz(v) (int)v.size()
typedef long long LL;
typedef double db;
template<class T>bool ckmax(T&x,T y){return x<y?x=y,1:0;}
template<class T>bool ckmin(T&x,T y){return x>y?x=y,1:0;}
#define rep(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
#define per(i,x,y) for(int i=x,i##end=y;i>=i##end;--i)
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
const int N=200005;
const int M=N<<2;
int n,m,V,f[M],a[N<<1],tot,IV,c[N],b[N<<1],ans,P[N];
#define mod 998244353
namespace math{
int inv[N],fac[N],ifc[N];
inline int qpow(int n,int k){int res=1;for(;k;k>>=1,n=1ll*n*n%mod)if(k&1)res=1ll*n*res%mod;return res;}
inline void fmod(int&x){x-=mod,x+=x>>31&mod;}
inline int comb(int n,int m){return n<m?0:1ll*fac[n]*ifc[m]%mod*ifc[n-m]%mod;}
void initmath(const int&n=N-1){
	inv[1]=1;for(int i=2;i<=n;++i)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
	fac[0]=1;for(int i=1;i<=n;++i)fac[i]=1ll*i*fac[i-1]%mod;
	ifc[n]=qpow(fac[n],mod-2);for(int i=n-1;i>=0;--i)ifc[i]=1ll*(i+1)*ifc[i+1]%mod;
}
}
using namespace math;

namespace poly{

int rev[M],lg,lim,rt[M];
void initpoly(const int&n){
	for(lg=0,lim=1;lim<=n;++lg,lim<<=1);
	for(int i=0;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
	for(int i=1;i<lim;i<<=1){
		const int w=qpow(3,(mod-1)/(i<<1));
		rt[i]=1;
		for(int j=1;j<i;++j)rt[i+j]=1ll*rt[i+j-1]*w%mod;
	}
}
void NTT(int*a,int op){
	if(!op)reverse(a+1,a+lim);
	for(int i=0;i<lim;++i)
		if(i>rev[i])swap(a[i],a[rev[i]]);
	for(int i=1;i<lim;i<<=1){
		for(int j=0;j<lim;j+=i<<1){
			for(int k=0;k<i;++k){
				const int X=a[j+k],Y=1ll*rt[i+k]*a[i+j+k]%mod;
				fmod(a[j+k]=X+Y),fmod(a[i+j+k]=X-Y+mod);
			}
		}
	}
	if(op)return;const int ilim=qpow(lim,mod-2);
	for(int i=0;i<lim;++i)a[i]=1ll*a[i]*ilim%mod;
}
#define clr(a,n) memset(a,0,sizeof(int)*(n))
#define cpy(a,b,n) memcpy(a,b,sizeof(int)*(n))
void poly_mul(int*f,int*g,int*ans,int n,int m){
	static int A[M],B[M];initpoly(n+m);
	cpy(A,f,n),clr(A+n,lim-n),NTT(A,1);
	cpy(B,g,m),clr(B+m,lim-m),NTT(B,1);
	for(int i=0;i<lim;++i)A[i]=1ll*A[i]*B[i]%mod;
	NTT(A,0),cpy(ans,A,n+m-1);
}
void dao(int*g,int*f,int n){
	for(int i=0;i<n-1;++i)g[i]=1ll*(i+1)*f[i+1]%mod;g[n-1]=0;
}
void poly_inv(int*g,int*f,int n){
	static int A[M],B[M];
	if(n==1)return g[0]=qpow(f[0],mod-2),void();
	int m=(n+1)>>1;
	poly_inv(g,f,m),initpoly(n<<1);
	cpy(A,f,n),clr(A+n,lim-n),cpy(B,g,m),clr(B+m,lim-m);
	NTT(A,1),NTT(B,1);
	for(int i=0;i<lim;++i)A[i]=1ll*B[i]*(2-1ll*A[i]*B[i]%mod+mod)%mod;
	NTT(A,0),cpy(g,A,n);
}

#define lc (p<<1)
#define rc (p<<1|1)
int pool[N<<6],*mem=pool,*ev[M];
void eva_mul(int*f,int*g,int*ans,int n,int m){
	static int A[M],B[M];initpoly(n);
	cpy(A,f,n),clr(A+n,lim-n),NTT(A,1);
	cpy(B,g,m),clr(B+m,lim-m),NTT(B,1);
	for(int i=0;i<lim;++i)A[i]=1ll*A[i]*B[i]%mod;
	NTT(A,0),cpy(ans,A+m-1,n-m+1);
}
void eva_solve1(int l,int r,int p,int*a){
	ev[p]=mem,mem+=r-l+1;
	if(r-l==1)return ev[p][0]=mod-a[l],ev[p][1]=1,void();
	int mid=(l+r)>>1;
	eva_solve1(l,mid,lc,a);
	eva_solve1(mid,r,rc,a);
	poly_mul(ev[lc],ev[rc],ev[p],mid-l+1,r-mid+1);
}
void eva_solve2(int l,int r,int p,int*h,int*f){
	if(r-l==1)return h[l]=f[0],void();
	int mid=(l+r)>>1,*al,*ar;
	al=mem,mem+=mid-l,ar=mem,mem+=r-mid;
	eva_mul(f,ev[rc],al,r-l,r-mid+1);
	eva_mul(f,ev[lc],ar,r-l,mid-l+1);
	eva_solve2(l,mid,lc,h,al);
	eva_solve2(mid,r,rc,h,ar);
}
void poly_eva(int*g,int*f,int*a,int n,int m){
	static int A[M];
	n=max(n,m);
	eva_solve1(0,n,1,a);
	reverse(ev[1],ev[1]+n+1);
	poly_inv(A,ev[1],n),reverse(A,A+n);
	poly_mul(A,f,A,n,n),cpy(A,A+n,n);
	eva_solve2(0,n,1,g,A);
	for(int i=0;i<m;++i)fmod(g[i]=1ll*g[i]*a[i]%mod+f[0]);
	for(int i=m;i<n;++i)g[i]=0;
}
void poly_sqa(int*g,int*f,int n){
	initpoly(n<<1);
	NTT(f,1);
	for(int i=0;i<lim;++i)g[i]=1ll*f[i]*f[i]%mod;
	NTT(g,0);
}
void poly_qpow(int*g,int *f,int k,int n){
	static int A[M];
	cpy(A,f,n),g[0]=1;
	for(;k;k>>=1,poly_sqa(A,A,n),clr(A+n,n))
		if(k&1)poly_mul(g,A,g,n,n),clr(g+n,n);
}
void newton(int*g,int n){
	static int A[M],B[M],C[M];
	if(n==1)return g[0]=0,void();
	newton(g,(n+1)>>1);
	clr(A,n),A[0]=1;
	for(int i=0;i<n;++i)A[i]=(A[i]-2ll*g[i]%mod+mod)%mod;
	clr(B,n),poly_qpow(B,g,V-1,n);
	for(int i=1;i<n;++i)A[i]=(A[i]+1ll*V*B[i-1]%mod)%mod;
	clr(C,n),poly_inv(C,A,n);
	
	poly_mul(B,g,B,n,n),clr(B+n,n);
	for(int i=0;i<n;++i)A[i]=g[i];
	poly_sqa(A,A,n);
	for(int i=0;i<n;++i)fmod(A[i]=g[i]-A[i]+mod);
	fmod(A[1]+=mod-1);
	for(int i=1;i<n;++i)fmod(A[i]+=B[i-1]);
	poly_mul(A,C,A,n,n);
	
	for(int i=0;i<n;++i)fmod(g[i]+=mod-A[i]);
}
void calcf(int*f,int n){
	static int A[M],B[M];
	if(V>=127){
		f[0]=1;
		for(int k=1;k<=m;++k){
			for(int i=0;i<=k/V;++i){
				int tmp=1ll*comb(k,i)*comb(2*k-V*i-1,k-i*V)%mod;
				fmod(f[k]+=i&1?mod-tmp:tmp);
			}
		}
		return;
	}
	newton(A,n+1),dao(f,A,n+1);
	for(int i=0;i<n;++i) A[i]=A[i+1];
	clr(B,n),poly_inv(B,A,n);
	poly_mul(f,B,f,n,n),clr(f+n,n);
}

}

void solve(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	int p=1ll*l*(n-r+1)%mod*IV%mod,q=mod+1-p;
	P[tot]=p,a[tot++]=1ll*p*qpow(q,mod-2)%mod;
	solve(l,mid),solve(mid+1,r);
}

signed main(){
	math::initmath();
	n=read(),m=read(),V=read()+2;
	poly::calcf(f,m+1);
	IV=qpow(1ll*n*(n+1)/2%mod,mod-2);
	solve(1,n);
	for(int i=0,j=1;i<=m;++i,j=1ll*j*V%mod)
		c[i]=1ll*comb(m,i)*(j+mod-f[i])%mod*qpow(j,mod-2)%mod;
	poly::poly_eva(b,c,a,m+1,tot);
	for(int i=0;i<tot;++i)fmod(ans+=1ll*b[i]*qpow(mod+1-P[i],m)%mod);
	cout<<ans<<'\n';
}
    • 1

    「EZEC-7」线段树

    信息

    ID
    6523
    时间
    500~3000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 34ms