2259 - I. 鐵路鋪設 | TIOJ INFOR Online Judge

TIOJ-2259.cpp

// Author : ysh
// 12/09/2022 Fri 16:29:56.33
// https://tioj.ck.tp.edu.tw/problems/2259
#include<bits/stdc++.h>
using namespace std;
const int R = (int) 1e9 + 7;
#define int long long
#include<square>
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin>>n;
    if(n == 1) {
        cout<<0;
        return 0;
    }
    vector<vector<int>>to({
        {0,1,0,0,1,0,0,0,0,0,0,1}, 
        {1,0,1,0,0,0,0,0,0,0,0,0}, 
        {1,0,1,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,1,1,0,0,1,0,0}, 
        {0,0,0,0,0,1,1,0,0,1,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,1,0}, 
        {1,0,1,0,0,0,0,0,0,0,0,0}, 
        {0,1,0,0,1,0,0,0,0,0,0,1}, 
        {0,0,0,0,0,0,0,1,1,0,0,0}, 
        {1,0,1,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,1,0}
        // {1,2,3,4,5,6,7,8,9,0,1,2}
        });
    vector<vector<int>>one({
        {1,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,0,0}, 
        {1,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,0,0}
        // {0,2,3,4,5,6,7,8,9,0,0,2}
        });
    t<int> tt(to), ff(one);
    tt.mod(R);ff.mod(R);
    auto ans = ((tt ^ (n - 1)) * ff);
    // vector<vector<int>>from({{1,4,11}, {0,2}, {0,2}, {}, {6,5,9}, {5,6,9}, {10}, {0,2}, {1,4,11}, {7,8}, {0,2}, {10}});
    // for(int i = 0;i<=11;i++) {
    //     for(auto &j : from.at(i)) {
    //         if(!to.at(i).at(j)) cerr<<i<<" "<<j<<"\n";
    //     }
    // }
    // return 1;
    // vector<vector<int>>f(2,vector<int>(from.size()));
    // f.at(1).at(0) = f.at(1).at(8) = 1;
    // for(int i = 0;i<n - 1;i++) {
    //     int p = i & 1;
    //     for(int j = 0;j<=from.size() - 1;j++) {
    //         f.at(p).at(j) = 0;
    //         for(int &i : from.at(j)) {
    //             f.at(p).at(j) += f.at(!p).at(i);
    //         }
    //         f.at(p).at(j) = f.at(p).at(j) % R;
    //     }
    // // for(auto i : f.at(p)) cerr<<i<<" "; cerr<<"\n";
    // }
    cout<<(ans.f.at(1).at(0) + ans.f.at(4).at(0) + ans.f.at(11).at(0)) % R;
    return 0;
}