2019牛客暑期多校训练营（第九场）A：Power of Fibonacci（斐波拉契幂次和）

题意：求Σfi^m%p。 zoj上p是1e9+7，牛客是1e9；对于这两个，分别有不同的做法。

前者利用公式，公式里面有sqrt(5)，我们只需要二次剩余求即可。后者mod=1e9，5才mod下没有二次剩余，所以不能这么做了。可以分解mod，然后利用循环节搞。

zoj：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = ;

const LL MOD = ;

LL fac[N],A[N],B[N];

void Init()

{

    fac[] = ;

    for(int i=; i<N; i++)

        fac[i] = fac[i-] * i % MOD;

    A[] = B[] = ;

    for(int i=; i<N; i++)

    {

        A[i] = A[i-] *  % MOD;

        B[i] = B[i-] *  % MOD;

    }

}

LL quick_mod(LL a,LL b,LL MOD)

{

    LL ans = ;

    a %= MOD;

    while(b){

        if(b&){

            ans = ans * a % MOD;

            b--;

        }

        b>>=; a = a * a % MOD;

    }

    return ans;

}

LL Solve(LL n,LL k)

{

    LL ans = ;

    for(int r=; r<=k; r++)

    {

        LL t = A[k-r] * B[r] % MOD;

        LL x = fac[k];

        LL y = fac[k-r] * fac[r] % MOD;

        LL c = x * quick_mod(y,MOD-,MOD) % MOD;

        LL tmp = t * (quick_mod(t,n,MOD) - ) % MOD * quick_mod(t-,MOD-,MOD) % MOD;

        if(t == ) tmp = n % MOD;

        tmp = tmp * c % MOD;

        if(r & ) ans -= tmp;

        else      ans += tmp;

        ans %= MOD;

    }

    LL m = quick_mod(,MOD-,MOD);

    ans = ans * quick_mod(m,k,MOD) % MOD;

    ans = (ans % MOD + MOD) % MOD;

    return ans;

}

int main()

{

    int T;

    LL n,k;

    Init();

    scanf("%d",&T);

    while(T--)

    {

        cin>>n>>k;

        cout<<Solve(n,k)<<endl;

    }

    return ;

}

牛客：你可以不熟悉斐波拉契的循环节具体怎么求，但是只要知道mod=p^a，fib[]%mod的循环节小于p^(a-1)* (2*p+2)。

而1e9计较特殊，1e9=2^9*5^9，这两部分对应的循环节都不是很大，所以我们可以分别求，然后中国剩余定理合并啊，就可以水过去了。

(但是我的代码怎么这么慢啊

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int Mod=1e9;

int md[]={,};

int f[],ans[];

int qpow(int a,int x,int p)

{

    int res=; while(x){

        if(x&) res=1LL*res*a%p;

        x>>=; a=1LL*a*a%p;

    } return res;

}

void exgcd(int a,int b,int &x,int &y)

{

    if(b==){ x=; y=; return;}

    exgcd(b,a%b,y,x); y-=a/b*x;

}

int rev(int a,int b)

{

    int x,y; exgcd(a,b,x,y);

    x=(x%b+b)%b; return x;

}

int main()

{

    int N,M;

    scanf("%d%d",&N,&M);

    rep(k,,) {

        f[]=; f[]=; int j=;

        for(;;j++){

            f[j]=(f[j-]+f[j-]);

            if(f[j]>=md[k]) f[j]-=md[k];

            if(f[j]==&&f[j-]==) {

                j--; break;

            }

        }

        int P=N/j;

        for(int i=;i<j;i++) {

            int t=qpow(f[i],M,md[k]);

            ans[k]=(ans[k]+1LL*t*(P+(i<=N%j)))%md[k];

        }

    }

    int res=(1LL*ans[]*md[]%Mod*rev(md[],md[])%Mod+1LL*ans[]*md[]%Mod*rev(md[],md[])%Mod)%Mod;

    printf("%d\n",res);

    return ;

}

巴特西

2019牛客暑期多校训练营（第九场）A：Power of Fibonacci（斐波拉契幂次和）

最新文章

热门文章