题目概述

$f_1=A,f_2=B,f_n=Cf_{n-2}+Df_{n-1}+\lfloor{P\over n}\rfloor$ ，求 $f_n$ 。

解题报告

这可能是斯波题吧……除法分块然后每个块里做矩乘就行了，注意一下 $n>P$ 的情况。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MOD=1e9+7;

int te,A,B,C,D,P,n;
struct Matrix{
    int r,c,s[3][3];
    inline void zero(int R,int C) {r=R;c=C;for (int i=0;i<R;i++) for (int j=0;j<C;j++) s[i][j]=0;}
    inline void unit(int n) {zero(n,n);for (int i=0;i<n;i++) s[i][i]=1;}
}f,T;
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline Matrix operator * (const Matrix &a,const Matrix &b){
    static Matrix c;c.zero(a.r,b.c);
    for (int i=0;i<a.r;i++)
        for (int j=0;j<b.c;j++)
            for (int k=0;k<a.c;k++)
                AMOD(c.s[i][j],(LL)a.s[i][k]*b.s[k][j]%MOD);return c;
}

inline Matrix Pow(Matrix w,int b) {static Matrix s;s.unit(w.r);for (;b;b>>=1,w=w*w) if (b&1) s=s*w;return s;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d%d%d%d%d%d",&A,&B,&C,&D,&P,&n);
        if (n==1) {printf("%d\n",A);continue;}if (n==2) {printf("%d\n",B);continue;}
        f.zero(1,3);f.s[0][0]=A;f.s[0][1]=B;f.s[0][2]=1;
        T.zero(3,3);T.s[0][1]=C;T.s[1][1]=D;T.s[1][0]=T.s[2][2]=1;
        for (int l=3,r;l<=n&&l<=P;l=r+1) {r=P/(P/l);if (r>n) r=n;T.s[2][1]=P/l;f=f*Pow(T,r-l+1);}
        if (n>P) T.s[2][1]=0,f=f*Pow(T,n-max(P,2));printf("%d\n",f.s[0][1]);
    }
    return 0;
}