AtCoder s8pc_3_g

· · 题解

题目链接

答案就是 fibonacci 数列的 n-1 阶前缀和的第 m 项，即

[x^{m-1}] \frac{1}{(1-x-x^2)(1-x)^{n-1}}

以下都将 n,m 同时减一。考虑进行一下分式分解，将原问题写为

[x^m]\left( \frac{f(x)}{1-x-x^2}+\frac{g(x)}{(1-x)^n}\right)

当然这两个分式都要求是真分式，满足条件

f(x)(1-x)^n+g(x)(1-x-x^2)=1

根据 EI 的方法，两边同时对 (1-x)^n 取模得到

g(x)(1-x-x^2) \equiv 1 \pmod{(1-x)^n} g(1-z)(-1+3z-z^2)\equiv 1 \pmod {z^n}

注意，我们并不需要实际地求出 g(z)，只需要知道 g(1-z) 就足够了（为了防止混淆形式变量，这里区分开了 z 和 u）：

\frac{g(z)}{(1-z)^n}=\sum_{i=0}^{n-1}\frac{[u^i]g(1-u)}{(1-z)^{n-i}}

然后就是要求出

f(x)=\frac{1-g(x)(1-x-x^2)}{(1-x)^n}

虽然看起来难以处理，但等式右边只需要保留到一次项。具体处理方法如下：

z^nf(1-z)=1-g(1-z)(-1+3z-z^2)

提取等式右边的 z^n 和 z^{n+1} 项系数，即对应 f(1-z) 的 z^0 和 z^1 项，然后再变回来即可。

代码如下（也许你会问为什么这么久才补代码，因为 shaber 评测要求答案必须换行输出，之前想破脑袋都没想到是这个问题）：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 200003
#define p 998244353
#define ll long long
using namespace std;

int inv[N];

struct mat{
    int a[2][2];
    inline mat(){ memset(a,0,sizeof(a)); }
}A;

inline mat operator * (const mat& lhs,const mat& rhs){
    mat res;
    for(int i=0;i!=2;++i)
    for(int j=0;j!=2;++j)
        res.a[i][j] = ((ll)lhs.a[i][0]*rhs.a[0][j]+(ll)lhs.a[i][1]*rhs.a[1][j])%p;
    return res;
}

inline mat power(mat a,ll t){
    mat res = mat();
    res.a[0][0] = res.a[1][1] = 1;
    while(t){
        if(t&1) res = res*a;
        a = a*a;
        t >>= 1;
    }
    return res;
}

int n,ans,c = 1;
ll m;
int f0,f1,g[N];

int main(){
    A.a[0][0] = A.a[0][1] = A.a[1][0] = 1;
    scanf("%d%lld",&n,&m);
    if(m==1){
        puts("1");
        return 0;
    }
    A = power(A,m-2);
    if(n==1){
        printf("%d\n",(A.a[0][0]+A.a[0][1])%p);
        return 0;
    }
    inv[1] = 1;
    for(int i=2;i<=n;++i) inv[i] = -(ll)(p/i)*inv[p%i]%p;
    --n,m = (m-1)%p;
    g[0] = -1,g[1] = -3;
    for(int i=2;i<n;++i) g[i] = (3ll*g[i-1]-g[i-2])%p;
    for(int i=n-1;~i;--i){ 
        ans = (ans+(ll)c*g[i])%p;
        c = (ll)c*(m+n-i)%p*inv[n-i]%p;
    }
    f0 = (-2ll*g[n-1]+(n>=2?g[n-2]:0))%p;
    f1 = -g[n-1];
    ans = (ans+(ll)f0*(A.a[0][0]+A.a[0][1])+(ll)f1*(A.a[1][0]+A.a[1][1]))%p;
    printf("%d\n",(ans+p)%p);
    return 0;   
}