2019牛客暑期多校训练营（第九场）The power of Fibonacci—

题意

求 $\displaystyle \sum_{i=1}^n F_i^m $，（$1 \leq n\leq 10^9,1 \leq m\leq 10^3$），答案对 $10^9$ 取模。

分析

显然，斐波那契数列在模意义下是有循环节的。

模 $10^9$ 本身的循环节为 $150000000$，还是很大，没意义。

设答案为求和的结果为 $ans$，根据中国剩余定理，要求 $ans \% p$，可先求 $ans \% p_1$ 和 $ans \% p_2$（其中 $p_1p_2 = p$，且 $p_1,p_2$ 互素），然后再合并回去。

设斐波那契数列模 $p$ 时的循环节长度为 $loop(p)$，$10^9 = 2^9 \cdot 5^9$，易知 $loop(512)=768$，$loop(1953125)=7812500$。

模数只拆成了两部分，甚至不用上中国剩余定理的模板。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll p = 1e9;

const ll p1 = , loop1 = , inv_p1 = ;

const ll p2 = , loop2 = , inv_p2 = ;

ll n, m;

ll qpow(ll a, ll b, ll p)

{

    ll ret = ;

    while(b)

    {

        if(b&)  ret = ret * a % p;

        a = a * a % p;

        b >>= ;

    }

    return ret;

}

ll fi(ll n, ll m, ll loop, ll p)

{

    if(n == )  return ;

    if(n == )  return ;

    ll yu = n % loop;

    ll ret = , tmp = ;

    if(yu == )  tmp=;

    if(yu == )  tmp=;

    ll a=, b=, c;

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

    {

        c = (a+b) % p;

        a = b;

        b = c;

        ret = (ret + qpow(c, m, p)) % p;

        if(i == yu) tmp = ret;

    }

    return (ret * (n / loop) % p + tmp) % p;

}

int main()

{

    scanf("%lld%lld", &n, &m);

    ll ans1 = fi(n, m, loop1, p1);

    ll ans2 = fi(n, m, loop2, p2);

    ll ans = (ans1 * p2 %p * inv_p2 %p  + ans2 * p1 % p * inv_p1 %p) % p;

    printf("%lld\n", ans);

}

参考链接：https://blog.csdn.net/ACdreamers/article/details/10983813

巴特西

2019牛客暑期多校训练营（第九场）The power of Fibonacci——循环节&&CRT

题意

分析

最新文章

热门文章