P6613 一阶微分方程 题解

· · 题解

乱糊不用脑子解方程做法，常数巨大。

题目指路。

解方程

下面推导省略同余号。

首先根据解方程的习惯，设 y=F(x)，有方程：

\dfrac{\mathrm{d} y}{\mathrm{d} x}=A(x)e^{y-1}+B(x)

如果这里不是 e^{y-1} 而是一个 y^n，方程就是一个伯努利方程，特别好解。

因此，考虑换元，设 t=e^{y-1}，则 y=\ln t+1。

根据边界条件，当 x=0 时，y=1，故此时 t=1。

原方程可化为：

\dfrac{\mathrm{d}(\ln t+1)}{\mathrm{d} x}=A(x)t+B(x)

我们有 \mathrm{d}(\ln t+1)=\dfrac 1 t \mathrm{d}t，移项得到：

\dfrac{\mathrm{d}t}{\mathrm{d} x}=A(x)t^2+B(x)t

还看不出来？再移项变成 \dfrac{\mathrm{d}t}{\mathrm{d} x}-B(x)t=A(x)t^2。这是一个伯努利方程！接下来就好解了。

两边同时除以 t^2，得到：

t^{-2}\dfrac{\mathrm{d}t}{\mathrm{d} x}-t^{-1}B(x)=A(x)

换元，设 k=t^{-1}，则 t=\dfrac 1 k。根据边界条件得到当 x=0 时 k=1。

求导得到下式：

\dfrac{\mathrm{d}k}{\mathrm{d} x}=-t^{-2}\dfrac{\mathrm{d}t}{\mathrm{d} x}

带入上式，有：

\dfrac{\mathrm{d}k}{\mathrm{d} x}+B(x)k=-A(x)

这是一个关于 k 的一阶线性微分方程。有通解：

k=C e^{-\int P(x) \mathrm{d}x}+e^{-\int P(x) \mathrm{d}x} \int Q(x) e^{\int P(x) \mathrm{d}x}\mathrm{d}x

具体解法是采用常数变易法化成一阶齐次微分方程然后求解。

考虑 C 的取值。我们发现当 x=0 时 \int Q(x) e^{\int P(x)\mathrm{d}x}\mathrm{d}x=0,e^{-\int P(x) \mathrm{d}x}=1，又由此时 k=1 得到 C=1。

因此，使用上面的公式得到 k，多项式求逆得到 t，多项式求对数得到 y-1，即可求出答案。

总时间复杂度 O(n\log n)，但带个 6 倍左右的常数。喜提全站最劣解。不过一点脑子不用，套板子就行。

附上代码

省略多项式板子，其中 inte 为不定积分。

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    A.len=B.len=n;
    F(i,0,n) cin>>A.num[i];
    F(i,0,n) cin>>B.num[i];
    poly x,y;
    B=B.inte();
    x=B.exp();
    y=(-1*B).exp();
    x=x*(-1*A);
    x.resize(n);
    x=x.inte();
    x.resize(n);
    res=y+y*x;
    res.resize(n);
    res=res.inv();
    res.resize(n);
    res=res.ln();
    res.resize(n);
    res=res+1;
    res.output();
    return 0;
}

完结撒花，不喜勿喷 qwq~