简单分析，不难得到以下转移——
$$
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
Wow, incredible blog structure! How long have you been blogging for?
you made blogging glance easy. The overall look of your web site is fantastic, let alone the content material!
You can see similar here sklep online
I will immediately snatch your rss as I can’t in finding your email subscription hyperlink or
newsletter service. Do you’ve any? Kindly permit me realize so that I may subscribe.
Thanks. I saw similar here: Najlepszy sklep
I’ve been browsing online more than 2 hours today, yet I never
found any interesting article like yours. It’s pretty worth enough for me.
In my view, if all website owners and bloggers made good content as you did, the internet will be much more useful than ever before.
I saw similar here: Najlepszy sklep
Hi! Do you know if they make any plugins to assist with
Search Engine Optimization? I’m trying to get my blog to rank for
some targeted keywords but I’m not seeing very good success.
If you know of any please share. Kudos! You can read similar blog here: Sklep online
También puede personalizar el monitoreo para ciertas aplicaciones, e inmediatamente comenzará a capturar instantáneas de la pantalla del teléfono con regularidad. https://www.mycellspy.com/es/tutorials/how-spy-app-remotely-monitor-someone-phone-activity/