結果

問題 No.569 3 x N グリッドのパスの数
コンテスト
ユーザー mamekin
提出日時 2017-09-10 10:18:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,386 bytes
コンパイル時間 1,691 ms
コンパイル使用メモリ 122,528 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-07 12:32:34
合計ジャッジ時間 3,143 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

const int MOD = 1000000007;

// 行列の積
template <class T>
vector<vector<T> > matrixProduct(const vector<vector<T> >& x, const vector<vector<T> >& y)
{
    int a = x.size();
    int b = x[0].size();
    int c = y[0].size();
    vector<vector<T> > z(a, vector<T>(c, 0));
    for(int i=0; i<a; ++i){
        for(int j=0; j<c; ++j){
            for(int k=0; k<b; ++k){
                z[i][j] += x[i][k] * y[k][j];
                z[i][j] %= MOD;
            }
        }
    }
    return z;
}

// 行列の累乗
template <class T>
vector<vector<T> > matrixPower(const vector<vector<T> >& x, long long k)
{
    int n = x.size();
    vector<vector<T> > y(n, vector<T>(n, 0));
    for(int i=0; i<n; ++i)
        y[i][i] = 1; // 積の単位元

    vector<vector<T> > z = x;
    while(k > 0){
        if(k & 1)
            y = matrixProduct(y, z);
        z = matrixProduct(z, z);
        k >>= 1;
    }
    return y;
}

string getNextState(const string& s, bitset<32> bs)
{
    int n = s.size();
    for(int i=0; i<n-1; ++i){
        if(s[i+1] != '.' && bs[i] && bs[i+1])
            return "";
    }

    string t = s;
    int i = 0;
    char c = 'Z';
    while(i < n - 1){
        int j = i;
        while(j < n - 1 && bs[j])
            ++ j;
        if(i < j){
            if(t[i] == t[j]){
                if(t[i] == '.'){
                    t[i] = t[j] = c;
                    -- c;
                }
                else{
                    return "";
                }
            }
            else{
                if(t[i] == '.' || t[j] == '.'){
                    swap(t[i], t[j]);
                }
                else{
                    char x = t[i];
                    char y = t[j];
                    replace(t.begin(), t.end(), x, y);
                    t[i] = t[j] = '.';
                }
            }
        }
        i = j + 1;
    }

    c = 'A';
    map<char, char> to;
    for(int i=0; i<n; ++i){
        if(t[i] != '.'){
            if(to.find(t[i]) == to.end()){
                to[t[i]] = c;
                ++ c;
            }
            t[i] = to[t[i]];
        }
    }

    return t;
}

int main()
{
    long long n;
    cin >> n;

    vector<string> state = { "A...", "...A" };
    for(unsigned i=0; i<state.size(); ++i){
        for(int j=0; j<(1<<3); ++j){
            string s = getNextState(state[i], j);
            if(s != "" && find(state.begin(), state.end(), s) == state.end())
                state.push_back(s);
        }
    }

    int m = state.size();
    vector<vector<long long> > mat(m, vector<long long>(m, 0));
    for(int i=0; i<m; ++i){
        for(int j=0; j<(1<<3); ++j){
            string s = getNextState(state[i], j);
            if(s != ""){
                int k = find(state.begin(), state.end(), s) - state.begin();
                ++ mat[i][k];
            }
        }
    }

    mat = matrixPower(mat, n+1);
    cout << mat[1][0] << endl;

    return 0;
}
0