[hdu7085]Pty loves SegmentTree

简单分析，不难得到以下转移——
$$
f_{n}=\begin{cases}1&(n=1)\\B\sum_{i=1}^{n-1}f_{i}f_{n-i}&(n\le k)\\B\sum_{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_{n\ge 1}f_{n}x^{n}$，那么即
$$
F(x)=B\cdot F^{2}(x)+(A-B)f_{k}x^{k}F(x)+x
$$
记$C=(A-B)f_{k}$，代入求根公式即
$$
F(x)=\frac{-(Cx^{k}-1)\pm\sqrt{(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))'$，将每一项分别代入，两式即分别为
$$
-2\left(2BF'(x)+Ckx^{k-1}\right)\left((Cx^{k}-1)^{2}-4Bx\right)\\\left(1-2BF(x)-Cx^{k}\right)\left(2C^{2}kx^{2k-1}-2Ckx^{k-1}-4B\right)
$$
将两者展开后整理，即
$$
\left(C^{2}kx^{2k-1}-Ckx^{k-1}-2B\right)F(x)-\left(C^{2}x^{2k}-2Cx^{k}-4Bx+1\right)F'(x)+\left(2Ckx^{k}-Cx^{k}+1\right)=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 n\le 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\n",(sum[r]-sum[l-1]+mod)%mod);

28         }

29     }

30     return 0;

31 }

巴特西

[hdu7085]Pty loves SegmentTree

最新文章

热门文章