本文最后更新于:2020年4月20日 凌晨

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6442

定义序列{a}=(a0,a1,a2,)\{a\}=(a_0,a_1,a_2,\dots)

它的指数型生成函数为g{a}(x)=i=0aii!xig_{\{a\}}(x)=\sum_{i=0}^{\infty}\frac{a_i}{i!}x^i

cc是一个常数

定义序列{uc}=(c0,c1,c2,)\{u_c\}=(c^0,c^1,c^2,\dots),{ec}=(0,c1,0,c3,0,c5,)\{e_c\}=(0,c^1,0,c^3,0,c^5,\dots)

定义两个生成函数g{a},g{b}g_{\{a\}},g_{\{b\}}的卷积G(x)=(g{a}g{b})(x)=n=0(i+j=naii!bjj!)xnG(x)=(g_{\{a\}}*g_{\{b\}})(x)=\sum_{n=0}^{\infty}(\sum_{i+j=n}\frac{a_i}{i!}\frac{b_j}{j!})x^n(原题面省略了阶乘,可能是写错了?)

现在给三个正整数n,A,Bn,A,B,求G(x)=guAgeBG(x)=g_{u_A}*g_{e_{\sqrt{B}}}xnx^n前的系数乘上n!n!后的结果

赛中走了很多弯路,思路大概是这样的

首先用泰勒展开,可以看出

guA=eAx,geB=12(eBxeBx)g_{u_A}=e^{Ax},g_{e_B}=\frac{1}{2}(e^{\sqrt{B}x}-e^{-\sqrt{B}x})

所以G(x)=guAgeB=12(e(A+B)xe(AB)x)G(x)=g_{u_A}*g_{e_{\sqrt{B}}}=\frac{1}{2}(e^{(A+\sqrt{B})x}-e^{(A-\sqrt{B})x})

第n项系数为(A+B)n(AB)n2\frac{(A+\sqrt{B})^n-(A-\sqrt{B})^n}{2}

类似斐波那契数列也可以强行求出线性递推的式子然后矩阵快速幂,就是推得比较难受罢了==

更快的方法

不用泰勒展开,直接用二项式定理类似的凑一下就可以得到第nn项系数的式子,最后也不用推递推式,答案就是(A+B)n=x+yB(A+\sqrt{B})^n=x+y\sqrt{B}中去掉整数项xx,直接快速幂就做完了。

赛中代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,n,mod;
struct matrix
{
    ll mx[2][2];
    matrix()
    {
        memset(mx,0,sizeof(mx));
    }
    void clear()
    {
        memset(mx,0,sizeof(mx));
    }
    void init()
    {
        memset(mx,0,sizeof(mx));
        mx[0][0]=mx[1][1]=1;
    }
    friend matrix operator *(const matrix &a,const matrix &b)
    {
        matrix c;
        for(int i=0;i<2;++i)
            for(int k=0;k<2;++k)
                for(int j=0;j<2;++j)
                    c.mx[i][j]=(c.mx[i][j]+a.mx[i][k]*b.mx[k][j])%mod;
        return c;
    }
}A,ans;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&mod);
        ans.init();
        A.mx[0][0]=2*a%mod;A.mx[0][1]=1;
        A.mx[1][0]=(b-a*a%mod+mod)%mod;A.mx[1][1]=0;
        --n;
        while(n)
        {
            if(n&1) ans=ans*A;
            A=A*A;
            n>>=1;
        }
        ll pp=0;
        for(ll i=1;1LL*i*i<=b;++i)
        if(b%(i*i)==0)
            pp=i;
        printf("%d %I64d %I64d\n",1,ans.mx[0][0]*pp%mod,b/(pp*pp));
    }
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

线段树优化凸壳 上一篇
线段树优化建图 下一篇