FZU 第十六届程序设计竞赛_重现赛 & FOJ Problem 2314 宝宝会求导 题解

FZU 第十六届程序设计竞赛_重现赛 & FOJ Problem 2314 宝宝会求导

已知 \(\displaystyle f(x)={1\over e^{-x}+1}\)

求 \(x=0\) 处泰勒展开第 \(k\) 项系数 \(\mod (10^9+7)\)

已知该函数在 \(x=0\) 处泰勒展开式第 \(k\) 项系数为 \(\displaystyle {f^{(k)}(0)\over k!}\)

由于 \(({1\over k!})\mod (10^9+7)\) 可以 \(O(n)\) 求出，故直接考虑求解 \(f^{(k)}(0)\mod (10^9+7)\)

不妨设 \(\displaystyle y=f(x)={1\over e^{-x}+1}\Rightarrow {\text dy\over \text dx}=-{{\text d\over \text dx}(e^{-x}+1)\over (e^{-x}+1)^2}={(e^{-x}+1)-1\over (e^{-x}+1)^2}=y-y^2\)

再次求导可得 \(\displaystyle {\text d^2 y\over \text dx^2}={\text d\over \text dx}({\text dy\over \text dx})={\text dy\over \text dx}\cdot {\text d\over \text dy}({\text dy\over \text dx})={\text dy\over \text dx}\cdot {\text d\over \text dy}(y-y^2)=(1-2y)\cdot {\text dy\over \text dx}=(1-2y)(y-y^2)=y-3y^2+2y^3\)

进而可观察出规律，若设 \(\displaystyle {\text d^n y\over \text dx^n}=\sum_{i=0}^{n+1}a_iy^i\)

则 \(\displaystyle {\text d^{n+1} y\over \text dx^{n+1}}={\text d\over \text dx}({\text d^n y\over \text dx^n})={\text dy\over \text dx}\cdot ({\text d\over \text dy}\sum_{i=0}^{n+1}a_iy^i)\)

由于后面这个显然是个多项式函数，前面的我们之前求导得到为 \((y-y^2)\)

\(\therefore \displaystyle {\text d^{n+1} y\over \text dx^{n+1}}=(y-y^2)(\sum_{i=0}^{n+1}ia_iy^{i-1})=(1-y)(\sum_{i=0}^{n+1}ia_iy^i)\)

也就是说，我们可以根据之 \(n\) 阶导的 \(y\) 多项式系数，可以 \(O(n)\) 地推出 \((n+1)\) 阶导的 \(y\) 多项式系数

又 \(\because \displaystyle y|_{x=0}={1\over 2}\)

故我们可以 \(O(n^2)\) 地求解出问题结果

用 Ans[MAXN] 储存 \(k\) 阶导的答案， INV2[MAXN] 储存 \(({1\over 2})^k \mod (10^9+7)\) , Frac[MAXN] 储存 \(({1\over k!})\mod (10^9+7)\) ， F[MAXN] 储存当前阶导数的 \(y\) 多项式系数

可以先 \(O(n)\) 预处理出 \(({1\over 2})^k \mod (10^9+7)\) 与 \(k!\mod (10^9+7)\)

使用欧拉定理与快速幂 \(({1\over 1000!})\equiv (1000!)^{(10^9+7)-1}(\mod 10^9+7)\) 求解出 \(({1\over 1000!})\mod (10^9+7)\) 。再反向扫回，求解出 \(({1\over k!})\mod (10^9+7)\)

接下来通过递推算出 F[MAXN] 从而求解 Ans[MAXN]

由于从递推关系可得，式子从 \(\displaystyle \sum_{i=0}^{n+1}a_iy^i\) 变为 \(\displaystyle (1-y)(\sum_{i=0}^{n+1}ia_iy^i)\)

故写出代码：

    for(int i=1;i<=1000;i++){
        for(int j=1;j<=i;j++) F[j]=j*F[j]%MOD;
        for(int j=i+1;j>=1;j--) F[j]=(F[j]-F[j-1]+MOD)%MOD;
    }

再加入刚刚求解的 INV2[MAXN],Frac[MAXN] 即可算出答案

    for(int i=1;i<=1000;i++){
        for(int j=1;j<=i;j++) F[j]=j*F[j]%MOD;
        for(int j=i+1;j>=1;j--) F[j]=(F[j]-F[j-1]+MOD)%MOD;
        for(int j=1;j<=i+1;j++) Ans[i]=(Ans[i]+F[j]*INV2[j]%MOD)%MOD;
        Ans[i]=Ans[i]*Frac[i]%MOD;
    }

最后主函数里面 \(O(1)\) 查询即可，总复杂度 \(O(n^2+T),T\) 为询问次数

【代码】

#include<iostream>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7,inv2=MOD+1>>1,MAXN=1024;//inv2 为 2 的逆元
ll Ans[MAXN];
inline ll fpow(ll a,ll x){//快速幂
    ll ans=1;
    for(;x;x>>=1,a=a*a%MOD) if(x&1) ans=ans*a%MOD;
    return ans;
}
inline void pre(){
    ll F[MAXN]={0},INV2[MAXN],Frac[MAXN];
    INV2[0]=Frac[0]=1;//初始化
    for(int i=1;i<=1010;i++){//多算一点，防炸
        INV2[i]=INV2[i-1]*inv2%MOD;
        Frac[i]=i*Frac[i-1]%MOD;
    }
    Frac[1000]=fpow(Frac[1000],MOD-2);
    for(int i=999;i>=0;i--)
        Frac[i]=Frac[i+1]*(i+1)%MOD;

    Ans[0]=inv2;//初始化
    F[1]=1;//0 阶导时，y 的多项式为 y，即 1*y^1
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=i;j++) F[j]=j*F[j]%MOD;
        for(int j=i+1;j>=1;j--) F[j]=(F[j]-F[j-1]+MOD)%MOD;
        for(int j=1;j<=i+1;j++) Ans[i]=(Ans[i]+F[j]*INV2[j]%MOD)%MOD;
        Ans[i]=Ans[i]*Frac[i]%MOD;
    }
}
int main(){
    pre();
    int N;
    while(cin>>N)
        cout<<Ans[N]<<endl;
    return 0;
}

FZU 第十六届程序设计竞赛_重现赛 & FOJ Problem 2314 宝宝会求导 题解

原文：https://www.cnblogs.com/JustinRochester/p/13302252.html