2017CCPC女生賽 hdu 6030 Happy Necklace

題目連結

分析：

一道推公式的題目。看着這個範圍就感覺是矩陣快速幂。

首先，可以把連續的素數中這個要求簡化成連續兩個和三個中的要求，很容易想。

定義： a[i],b[i] 分别表示長度為i，以red和blue結尾的串的個數。

然後，探索一下，發現 a[i]=a[i−1]+b[i−1],b[i]=a[i−2] ，最終答案兩個加一下就行了。

代碼：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <cmath>

using namespace std;

const int mod =  + ;

struct Mat {
    int n;
    long long a[][];

    Mat (int _n = ) : n(_n) {
        memset(a, , sizeof(a));
    }

    Mat operator *(const Mat& rhs) {
        Mat c;
        for (int k = ; k < ; k ++)
            for (int i = ; i < ; i ++)
                for (int j = ; j < ; j ++)
                    c.a[i][j] = (c.a[i][j] + a[i][k] * rhs.a[k][j] % mod) % mod;
        return c;
    }
}E;

void init() {
    for (int i = ; i < ; i ++)
        E.a[i][i] = ;
}

Mat qpow(Mat A, long long b) {
    Mat C = E;
    while (b) {
        if (b & ) C = C * A;
        A = A * A;
        b >>= ;
    }
    return C;
}

int main(int argc, char const *argv[]) {
    int T; cin>>T;
    init();
    while (T --) {
        long long n;
        scanf("%lld", &n);

        Mat A;
        A.a[][] = , A.a[][] = , A.a[][] = , A.a[][] = ;
        A.a[][] = , A.a[][] = , A.a[][] = , A.a[][] = ;
        A.a[][] = , A.a[][] = , A.a[][] = , A.a[][] = ;
        A.a[][] = , A.a[][] = , A.a[][] = , A.a[][] = ;

        A = qpow(A, n - );
        long long b[];
        b[] = , b[] = , b[] = , b[] = ;
        long long ans = ;
        for (int i = ; i < ; i ++)
            for (int j = ; j < ; j ++)
                ans = (ans + A.a[i][j] * b[j] % mod) % mod;

        printf("%d\n", (int)ans);
    }
    return ;
}