十七届同济大学程序设计预选赛-J

题目链接

十七届同济大学程序设计预选赛-J

思路

我们从这个开始考虑

$$\begin{aligned} F'_k(n)&=\sum_{i=1}^n(n-i)^kFib(i)\\ F'_k(n+1)&=\sum_{i=1}^n(n-i+1)^kFib(i)\\ \end{aligned}$$

上面两个式子做差得到

$$\begin{aligned} &F'_k(n+1)-F'_k(n)\\ &=\sum_{i=1}^{n}(n-i+1)^kFib(i)-\sum_{i=I}^N(n-i)^kFib(i)\\ &=\sum_{i=1}^{n}((n-i)+1)^k-(n-i)^kFib(i)\\ &=\sum_{i=1}^{n}\sum_{j=0}^{k-1}\binom{k}{j}Fib(i)\\ &=\sum_{j=0}^{n}\binom{k}{j}F'_j(n)\\ \end{aligned}$$

得到递推式子

$$\begin{aligned} &F'_k(n+1)=F'_k(n)+\sum_{j=0}^{n}\binom{k}{j}F'_j(n)\\ \end{aligned}$$

使用矩阵来得到所有的$F’_k(n)$,首先矩阵内需要有$Fib[i],Fib[i-1],F’_0[i],\dots,F’_k[i]$,$F’_0[i]=F’_[i-1]+Fib[i-2]+Fib[i-1]$,其他的用上面的式子推出，这样就得到一个k+3的矩阵。
得到上述的所有0~k的$F’_j[n]$之后，我们来还原，

$$\begin{aligned} F'_k(n)&=\sum_{i=1}^n(n-i)^kFib(i)\\ &=\sum_{j=0}^k(-1)^jn^{k-j}\binom{k}{k-j}F_j(n)\\ (-1)^kF_k(n)&=F'_k(n)-\sum_{j=0}^{k-1}(-1)^jn^{k-j}\binom{k}{k-j}F_j(n) \end{aligned}$$

这样就能求出$F_k(n)$了。

代码示例

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 998244353;
struct Mat{
    ll a[105][105];
    Mat(){
        memset(a,0,sizeof(a));
    }
    ll* operator[](int i){
        return a[i];
    }
};
int N = 104;
Mat operator * (Mat &a,Mat &b){
    Mat res;
    for(int i=0;i<N;i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                res[i][j] += a[i][k] * b[k][j] % mod;
            }
            res[i][j] %= mod;
        }
    }
    return res;
}
ll C[505][505];
ll f_b[505],f[505],pown[505];
Mat quick_pow(Mat a,ll p){
    Mat res;
    for(int i=0;i<N;i++)res[i][i]=1;
    while(p){
        if(p&1)res=a*res;
        a=a*a;
        p>>=1;
    }
    return res;
}
void init(){
    C[0][0]=1;
    for(int i=0;i<=500;i++){
        for(int j=0;j<=i;j++){
            C[i+1][j]+=C[i][j];
            C[i+1][j+1]+=C[i][j];
            C[i][j]%=mod;
            C[i+1][j+1]%=mod;
        }
    }
}
int main(){
    ll n,k;
    cin>>n>>k;
    init();
    pown[0]=1;
    for(int i=1;i<=k;i++){
        pown[i]=pown[i-1]*(n%mod)%mod;
    }
    N = k + 3;
    Mat a;
    a[0][0]=1;
    a[0][1]=1;
    a[1][0]=1;
    a[2][2]=1;
    a[2][0]=1;
    a[2][1]=1;//对应前三项斐波那契以及F'[0]
    for(int i=1;i<=k;i++){
        for(int j=0;j<=i;j++){
            a[i+2][j+2]=C[i][j];//对应后面的0~k
        }
    }
    a=quick_pow(a,n);
    for(int i=0;i<=k;i++){
        f_b[i]=a[i+2][1];
    }
    f[0]=f_b[0];
    for(int i=1;i<=k;i++)//转换
    {
        ll fi = f_b[i];
        ll flag = 1;
        for(int j=0;j<i;j++){
            flag = mod - flag;
            fi+=flag*C[i][j]%mod*pown[i-j]%mod*f[j]%mod;
        }
        fi%=mod;
        fi*=flag;
        f[i]=fi%mod;
    }
    cout<<f[k]<<endl;
}