• 周一. 5月 27th, 2024

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

《[hdu7085]Pty loves SegmentTree》有5个想法
  1. 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

  2. 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

  3. 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

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注