解题报告

题目中显然给出了一个卷积形式，所以我们移下项，凑凑常数，得到：

$$ {A(x)-A_0\over x}-A_1=A(x)A(x)-A_0^2\\ A(x)-A_0-A_1x=xA^2(x)-A_0^2x\\ xA^2(x)-A(x)+(A_1-A_0^2)x+A_0=0\\ A(x)={1\pm\sqrt{1-4x[(A_1-A_0^2)x+A_0]}\over 2x} $$

如果是加号，那么 $x\to0$ 的时候 $A(x)\to+\infty$ ，这就凉了，所以是减号：

$$ A(x)={1-\sqrt{1-4x[(A_1-A_0^2)x+A_0]}\over 2x} $$

那么前 $70$ 分是沙雕题，直接多项式开根+多项式求逆。

接下来是展开大法……用牛顿二项式定理：

$$ (x+y)^{\alpha}=\sum_{i=0}^{+\infty}{\alpha\choose i}x^iy^{\alpha-i}\\ {\alpha\choose i}={\prod_{j=0}^{i-1}(\alpha-i)\over i!} $$

先把那个根号展开：

$$ A(x)={1-\{1+\sum_{i=1}^{+\infty}{\prod_{j=0}^{i-1}({1\over 2}-j)\over i!}(-4)^ix^i[(A_1-A_0^2)x+A_0]^i\}\over 2x}\\ A(x)={-\sum_{i=1}^{+\infty}{{1\over 2}\prod_{j=1}^{i-1}({1\over 2}-j)\over i!}2^i(-2)^ix^i[(A_1-A_0^2)x+A_0]^i\over 2x}\\ A(x)=\sum_{i=1}^{+\infty}{2^{i-1}(2i-3)!!\over i!}x^{i-1}[(A_1-A_0^2)x+A_0]^i\\ $$

其中 $(2i-3)!!$ 表示双阶乘（隔一个数乘一次，即 $n!!=(n-2)!!\cdot n$），定义负数双阶乘为 $1$ 。

再把 $[(A_1-A_0^2)x+A_0]^i$ 展开（二项式定理）：

$$ A(x)=\sum_{i=1}^{+\infty}{2^{i-1}(2i-3)!!\over i!}x^{i-1}\sum_{j=0}^{i}{i\choose j}(A_1-A_0^2)^jx^jA_0^{i-j}\\ A(x)=\sum_{i=0}^{+\infty}{2^{i}(2i-1)!!\over (i+1)!}x^{i}\sum_{j=0}^{i+1}{i+1\choose j}(A_1-A_0^2)^jx^jA_0^{i+1-j} $$

把 $j=n-i$ 代入得到 $A_n$ ：

$$ A_n=\sum_{i=\lfloor{n\over 2}\rfloor}^{n}{2^{i}(2i-1)!!\over (i+1)!}{i+1\choose n-i}(A_1-A_0^2)^{n-i}A_0^{2i-n+1} $$

这样就可以 $O(n)​$ 了。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=2000000;

int A,B,n,MOD,fac[maxn+5],INV[maxn+5],ff[maxn+5],pw[3][maxn+5],ans;

#define FF(x) ((x)<0?1:ff[x])
inline void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i]*INV[i-1]%MOD;
    ff[0]=ff[1]=1;for (int i=2;i<=n;i++) ff[i]=(LL)FF(i-2)*i%MOD;
    pw[0][0]=pw[1][0]=1;for (int i=1;i<=n;i++) pw[0][i]=(pw[0][i-1]<<1)%MOD,pw[1][i]=(LL)pw[1][i-1]*A%MOD;
    pw[2][0]=1;int BA=(B+MOD-(LL)A*A%MOD)%MOD;for (int i=1;i<=n;i++) pw[2][i]=(LL)pw[2][i-1]*BA%MOD;
}
#define C(x,y) ((x)<(y)?0:(LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD)
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d%d",&A,&B,&n,&MOD);Make((n<<1)+1);
    for (int i=n>>1;i<=n;i++){
        int pre=(LL)FF((i<<1)-1)*pw[0][i]%MOD*INV[i+1]%MOD;
        AMOD(ans,(LL)pre*pw[1][(i<<1)-n+1]%MOD*pw[2][n-i]%MOD*C(i+1,n-i)%MOD);
    }printf("%d\n",ans);return 0;
}