[bzoj 3328] PYXFIB

bzoj 3328

思路

众所周知,$F$是可以矩阵递推的,令$$A=\left[\begin{matrix}1&1\\1&0\end{matrix}\right]$$
则$$F_n=A^n_{0, 0}$$

设$$\begin{split}f(x)
&=x^{-n}\cdot (xI+A)^n\\
&=\sum \limits_{i=0}^n\left({n\choose i}\cdot x^{-i}I\cdot A^i\right)
\end{split}$$

$$\begin{split}\sum \limits_{i=0}^{\lfloor\frac{n}{k}\rfloor}\left({n\choose i\cdot k}\cdot F_{i\cdot k}\right)
&=\sum \limits_{i=0}^{n}\left({n\choose i}\cdot F_i\cdot [k|i]\right)\\
&=\sum \limits_{i=0}^n\left({n\choose i}\cdot F_i\cdot \frac{1}{k}\cdot \sum \limits_{j=0}^{k-1}\omega^{ij}\right)\\
&=\frac{1}{k}\cdot \sum \limits_{j=0}^{k-1}\left(\sum \limits_{i=0}^n\left({n\choose i}\cdot A^i_{0, 0}\cdot \omega^{ij}\right)\right)\\
&=\frac{1}{k}\cdot \sum \limits_{j=0}^{k-1}f(\omega^{-j})_{0, 0}
\end{split}$$

日常bzoj不能用C++11差评

代码

#include <iostream>
#include <cstdio>
#include <vector>

typedef long long LL;
LL N;
int K, MOD, root, W[20010];

template <typename T> int ksm(int _, T __){
    int ans=1;
    while(__){
        if(__&1) ans=1LL*ans*_%MOD;
        _=1LL*_*_%MOD; __>>=1;
    }return ans;
}

int get_root(){
    std::vector<int>pri; int tmp=MOD-1;
    for(int i=2; i*i<MOD; i++) if(tmp%i==0){
        pri.push_back(i); while(tmp%i==0) tmp/=i;
    }
    if(tmp>1) pri.push_back(tmp);
    auto check=[&](int x){
        for(auto i: pri) if(ksm(x, (MOD-1)/i)==1) return false;
        return true;
    };
    for(int i=2; i<MOD; i++) if(check(i)) return i;
}

struct Matrix{
    int a[3][3];
    Matrix(){a[1][1]=a[1][2]=a[2][1]=a[2][2]=0;}
    int *operator [](int x){return a[x];}
}I, A;

Matrix operator +(Matrix a, Matrix b){
    for(int i=1; i<=2; i++) 
        for(int j=1; j<=2; j++) a[i][j]=(a[i][j]+b[i][j])%MOD;
    return a;
}
Matrix operator *(Matrix a, Matrix b){
    Matrix c;
    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
            for(int k=1; k<=2; k++)
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j]%MOD)%MOD;
    return c;
}
Matrix operator *(int a, Matrix b){
    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
            b[i][j]=1LL*a*b[i][j]%MOD;
    return b;
}
template <typename T> Matrix ksm(Matrix a, T b){
    Matrix ans; ans[1][1]=ans[2][2]=1;
    while(b){
        if(b&1) ans=ans*a;
        a=a*a; b>>=1;
    }
    return ans;
}

Matrix f(int x){return ksm(ksm(x, N), MOD-2)*ksm(x*I+A, N);}

int main(){
    I[1][1]=I[2][2]=A[1][1]=A[1][2]=A[2][1]=1;
    int T; scanf("%d", &T);
    while(T--){
        scanf("%lld%d%d", &N, &K, &MOD);
        root=get_root();
        W[0]=1;
        W[1]=ksm(root, (MOD-1)/K);
        for(int i=2; i<=K; i++) W[i]=1LL*W[i-1]*W[1]%MOD;
        int ans=0;
        for(int i=0; i<K; i++) ans=(ans+f(W[i])[1][1])%MOD;
        printf("%lld\n", 1LL*ans*ksm(K, MOD-2)%MOD);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注