题解 UVA10229 【Modular Fibonacci】

· · 题解

这道题目，说白了就是求\rm Fib (n) \% 2^m的答案而已。。。

这道题目，虽然m\le 20，最大模数也才2^{20}（也就意味着可以打表？我可没试过），于是，蒟弱的我决定用矩阵乘法水过此题。。。

我们先不考虑模数，对于\rm Fib (n)而言，我们可以推出以下公式：

\rm Fib$ $(n)=$ $\rm Fib$ $(n-1)*$ $\rm A

其中\rm A为矩阵\left[\begin{matrix}0 & 1\\1 & 1 \end{matrix}\right]

如果您有一定的矩阵乘法基础，相信您应该是可以懂的。

那么，我们假设\rm Fib(0)=\left[\begin{matrix}0 & 1 \end{matrix}\right]

目标为\rm Fib (n)= \rm Fib (0)* \rm A^n，因为矩阵乘法满足结合律，我们可以用快速幂来计算\rm Fib (0)* \rm A^n，该时间复杂度为O(2^3 log(n))。

至于取模，在矩阵加法和矩阵乘法时取一下2^m就好了。。。

讲了那么多，相信大家也应该会了吧。。。

#include<cstdio>
#include<cstring>
#include<iostream>
int n,m,mod;
long long l,r;
using namespace std;
void js(int f[2],int a[2][2])
{
    int c[2];
    memset(c,0,sizeof(c));
    for (int i=0;i<2;i++)
      for (int j=0;j<2;j++) c[i]=(c[i]+(long long)f[j]*a[j][i])%mod;
    memcpy(f,c,sizeof(c));
}
void rzt_js(int a[2][2])
{
    int c[2][2];
    memset(c,0,sizeof(c));
    for (int i=0;i<2;i++)
      for (int j=0;j<2;j++)
        for (int k=0;k<2;k++) 
          c[i][j]=(c[i][j]+(long long)a[i][k]*a[k][j])%mod;
    memcpy(a,c,sizeof(c));
}
int main()
{
    while (cin>>n>>m)
    {
        mod=1;
        for (int i=1;i<=m;i++) mod*=2;
        int f[2]={0,1},a[2][2]={{0,1},{1,1}};
        for (; n; n>>=1)
        {
            if (n&1) js(f,a);
            rzt_js(a);
        }
        printf("%d\n",f[0]);
    }
    return 0;
}