某模拟赛 T2 题解

· · 个人记录

通过找规律，发现 ans(n,k) 满足如下关系式：

(\dfrac 52-\dfrac{15}4k+\dfrac 54k^2)ans(n,k)+(\dfrac {5n-11}2-\dfrac{4n-29}4k+\dfrac 94k^2)ans(n,k-1)+(\dfrac{n^2-7n+12}{4}+\dfrac{2n-7}{2}k+k^2)ans(n,k-2)=0

据此计算即可。时间复杂度 O(k+\log n)。

核心代码：

int main(){
    //已经省略无关部分
    int n=0;
    for(int i=1;i<=len;i++)n=(10ll*n+a[i]-'0')%mod;
    for(int i=2;i<=k;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
    int v0=(5ll*n-11+mod)%mod*i2%mod;
    int v1=(5ll*n-29+mod)%mod*i4%mod;
    v1=(mod-v1)%mod;
    int v2=1ll*(mod-9)*i4%mod;
    int v3=(1ll*n*n%mod-7ll*n%mod+mod+12)%mod*i4%mod;
    int v4=(2ll*n%mod-7+mod)%mod*i2%mod;
    int i45=4ll*Power(5,mod-2)%mod;
    for(int i=3;i<=k;i++){
        int c0=1ll*i45*inv[i-1]%mod*inv[i-2]%mod;
        int c1=(v0+1ll*v1*i%mod+1ll*v2*i%mod*i)%mod;
        int c2=(v3+1ll*v4*i%mod+1ll*i*i)%mod;
        f[i]=(1ll*(mod-c1)*f[i-1]+1ll*(mod-c2)*f[i-2])%mod*c0%mod;
    }
    cout<<f[k];
}