• 周四. 6月 30th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu7085]Pty loves SegmentTree

admin

11月 28, 2021

简单分析,不难得到以下转移——
$$
f_{n}=egin{cases}1&(n=1)\Bsum_{i=1}^{n-1}f_{i}f_{n-i}&(nle k)\Bsum_{i=1}^{n-1}f_{i}f_{n-i}+(A-B)f_{k}f_{n-k}&(n>k)end{cases}
$$
(在$n<k$时,该式子即类似于为卡特兰数的递推式)

考虑生成函数,令$F(x)=sum_{nge 1}f_{n}x^{n}$​​,那么即
$$
F(x)=Bcdot F^{2}(x)+(A-B)f_{k}x^{k}F(x)+x
$$
记$C=(A-B)f_{k}$​,代入求根公式即
$$
F(x)=frac{-(Cx^{k}-1)pmsqrt{(Cx^{k}-1)^{2}-4Bx}}{2B}
$$
显然$F(0)=0$,那么代入即得到应取负号

令$Q^{2}(x)=(Cx^{k}-1)^{2}-4Bx$,将上式化简并整理即$Q(x)=1-2BF(x)-Cx^{k}$

将两边同时求导,即$Q'(x)=-2BF'(x)-Ckx^{k-1}$

注意到$2Q'(x)Q^{2}(x)=Q(x)(Q^{2}(x))’$​,将每一项分别代入,两式即分别为
$$
-2left(2BF'(x)+Ckx^{k-1}ight)left((Cx^{k}-1)^{2}-4Bxight)\left(1-2BF(x)-Cx^{k}ight)left(2C^{2}kx^{2k-1}-2Ckx^{k-1}-4Bight)
$$
将两者展开后整理,即
$$
left(C^{2}kx^{2k-1}-Ckx^{k-1}-2Bight)F(x)-left(C^{2}x^{2k}-2Cx^{k}-4Bx+1ight)F'(x)+left(2Ckx^{k}-Cx^{k}+1ight)=0
$$
考虑上式的$n-1$​次项系数并整理,即
$$
f_{n}=frac{2B(2n-3)f_{n-1}+C(2n-3k)f_{n-k}-C^{2}(n-3k)f_{n-2k}+[n=k+1]C(2k-1)}{n}
$$
为了方便,约定$forall nle 0,f_{n}=0$,由此直接递推即可(注意到在$n<k$时不需要$C$)

由此,即可线性预处理出所有$f_{i}$,进而前缀和即可快速查询

总时间复杂度为$o(n+q)$,可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 10000005
 4 #define mod 998244353
 5 #define ll long long
 6 int t,q,k,A,B,C,l,r,inv[N],f[N],sum[N];
 7 int main(){
 8     inv[0]=inv[1]=1;
 9     for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
10     scanf("%d",&t);
11     while (t--){
12         scanf("%d%d%d%d",&q,&k,&A,&B);
13         for(int i=1;i<N;i++){
14             if (i==1)f[1]=1;
15             else{
16                 f[i]=2LL*B*(2*i-3)%mod*f[i-1]%mod;
17                 if (i>k)f[i]=(f[i]+(ll)C*(2*i-3*k+mod)%mod*f[i-k])%mod;
18                 if (i>2*k)f[i]=(f[i]-(ll)C*C%mod*(i-3*k+mod)%mod*f[i-2*k]%mod+mod)%mod;
19                 if (i==k+1)f[i]=(f[i]+(ll)C*(2*k-1))%mod;
20                 f[i]=(ll)f[i]*inv[i]%mod;
21             }
22             if (i==k)C=(ll)(A-B+mod)*f[i]%mod;
23         }
24         for(int i=1;i<N;i++)sum[i]=(sum[i-1]+(ll)f[i]*f[i])%mod;
25         for(int i=1;i<=q;i++){
26             scanf("%d%d",&l,&r);
27             printf("%d
",(sum[r]-sum[l-1]+mod)%mod);
28         }
29     }
30     return 0;
31 }

View Code

发表评论

您的电子邮箱地址不会被公开。