【HNOI2002】【矩阵快速幂】公交车路线

仍然是学弟出的题目的原题@lher 学弟将题目改成了多组数据，n在ll范围内，所以我就只讲提高版的做法。

链接：https://www.luogu.org/problem/show?pid=2233

题意分析：看题目：）

解题思路：显然对于n为奇数的情况不存在任意路线。接下来我们进行观察数据，显然这题是要递推的。接下来通过暴力打表加手算，我们推出了这个公式：

f[i]=4*f[i-1]-2*f[i-2],f[1]=2,f[2]=8，然后构造对应矩阵进行矩阵快速幂即可得到答案。时间效率\( O ( 2^3 \lg n) \)。

附AC代码：

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long
#define mod 10007
using namespace std;
struct zxy{
    ll a[][];
}jichu,a,b;
ll n;
inline ll in(){
    ll x=,f=;
    char ch=getchar();
    while(ch<''||ch>'') {if(ch=='-') f=-; ch=getchar();}
    while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
    return x*f;
}
inline zxy mult(zxy a,zxy b){
    zxy c;
    memset(c.a,,sizeof(c.a));
    for (int i=; i<=; ++i)
        for (int j=; j<=; ++j)
            for (int k=; k<=; ++k)
                c.a[i][j]+=(a.a[i][k]*b.a[k][j]+*mod)%mod,c.a[i][j]=(c.a[i][j]+*mod)%mod;
    return c;
}
inline zxy ksm(zxy a,ll k){
    if (k==) return jichu;
    if (k==) return a;
    zxy tt=ksm(a,k>>);
    if (k&) return mult(a,mult(tt,tt));
    return mult(tt,tt);
}
int main(){
    int T=in();
    memset(jichu.a,,sizeof(jichu.a));
    memset(b.a,,sizeof(b.a));
    memset(a.a,,sizeof(a.a));
    jichu.a[][]=jichu.a[][]=;
    b.a[][]=;b.a[][]=;
    a.a[][]=;a.a[][]=-+mod,a.a[][]=;
    while(T--){
        n=in();
        if (n&) printf("0\n");
        else{
            n=n/-;
            if (n<) printf("%lld\n",b.a[n][]);
            else{ zxy ans=mult(ksm(a,n-),b);printf("%lld\n",ans.a[][]);}
        }
    }
    return ;
}

本文由Melacau编写，Melacau代表M星向您问好，如果您不是在我的博客http://www.cnblogs.com/Melacau上看到本文，请您向我联系，email:[e-mail].