TIOJ 1705

[naive ice]

https://tioj.ck.tp.edu.tw/problems/1705
有想到是矩陣快速冪的題目
但是想不到該怎麼設計矩陣
2^12 的矩陣應該太大了

[tidal cosmos]

試試矩陣存C^6_2的所有組合?

[naive ice]

確實是這樣

[tidal cosmos]

oh

2^12這個真的會超時嗎？ :v

[naive ice]

會

矩陣乘法

n³

怎

[tidal cosmos]

我剛剛算是63*2^18 :v

[naive ice]

（？

矩陣乘法就 2^36 了

[tidal cosmos]

log_2(2^63) * 矩陣乘法
矩陣乘法 = 矩陣 (2^6^2) * 2^6

[naive ice]

矩陣乘法為什麼是 2⁶

[tidal cosmos]

枚舉1~6的洞是否要挖

[naive ice]

矩陣大小 2^12
要怎麼做出 2^6 的乘法（？

你的矩陣乘法是拿怎樣的矩陣去乘

直接枚舉的話就只能線性乘吧

要矩陣快速冪就得建 2^12 × 2^12 的轉移矩陣（？

[tidal cosmos]

我原本是想用2^6的矩陣當作所有情況的數量
然後用2^6*2^6的轉移矩陣

[naive ice]

但是需要存兩排

狀態數是 2^12

沒辦法只用 i-1 排找到 i 排吧

[tidal cosmos]

:o

對耶

我燒爛

[naive ice]

大概是先把本來就不合法的狀態去掉

這樣狀態數就會變超少

[naive ice]

寫是寫出來了

但是 WA

這超難 debug

int n, m;
vector<int> masks;

struct matrix {
    vector<vector<int>> cont;

    matrix(int _n, int _m) {
        for (int i = 0; i < _n; i++)
            cont.pb(vector<int>(_m, 0));

    }

    matrix(int _n) {
        for (int i = 0; i < _n; i++)
            cont.pb(vector<int>(_n, 0));
        for (int i = 0; i < _n; i++)
            cont[i][i] = 1;
    }

    matrix operator *(matrix _a) {
        matrix res(SZ(cont), SZ(_a.cont[0]));

        for (int i = 0; i < SZ(cont); i++) {
            for (int j = 0; j < SZ(_a.cont[0]); j++) {
                res.cont[i][j] = 0;
                for (int k = 0; k < SZ(_a.cont); k++)
                    res.cont[i][j] += cont[i][k] * _a.cont[k][j];
                res.cont[i][j] %= P;
            }
        }

        return res;
    }

    void operator %=(const int P) {
        for (auto &col: cont)
            for (auto &it: col)
                it %= P;
    }


    int operator () (){
        int res = 0;
        for (auto &col: cont)
            for (auto &it: col)
                res += it;
        return res;
    }
};

bool check(int i) {
    return (i >= 0 && i < 6);
}

matrix make_T() {
    matrix res(SZ(masks), SZ(masks));

    for (int i = 0; i < SZ(masks); i++) {
        int mask1 = masks[i] >> 6; // i - 1
        int mask2 = masks[i] & 0b111111; // i
        for (int j = 0; j < SZ(masks); j++) {
            int mask3 = masks[j] >> 6; // i - 2
            int mask4 = masks[j] & 0b111111; // i - 1

            res.cont[i][j] = mask4 == mask1;

            for (int i = 0; i < 6; i++) if (mask2 & (1 << i)) {
                if (check(i - 2) && (mask4 & (1 << (i - 2))))
                    res.cont[i][j] = 0;
                if (check(i + 2) && (mask4 & (1 << (i + 2))))
                    res.cont[i][j] = 0;
                if (check(i - 1) && (mask3 & (1 << (i - 1))))
                    res.cont[i][j] = 0;
                if (check(i + 1) && (mask3 & (1 << (i + 1))))
                    res.cont[i][j] = 0;
            }
            // cout << res.cont[i][j] << ' ';
        }
        // cout << endl;
    }
    return res;
}

template<typename T>
T fpow(T a, int b, int P) {
    T res(SZ(masks));
    
    while (b) {
        if (b % 2) {
            res = res * a;
            res %= P;
        }
        a = a * a;
        a %= P;
        b >>= 1;
    }
    return res;
}

void sol() {
    cin >> n;

    if (n == 1) {
        int ans = 0;
        for (int mask = 0; mask < (1 << 6); mask++)
            ans += __builtin_popcount(mask) == 2;
        cout << ans << endl;
        return;
    }
    
    for (int mask1 = 0; mask1 < (1 << 6); mask1++) {
        if (__builtin_popcount(mask1) != 2)
            continue;
        for (int mask2 = 0; mask2 < (1 << 6); mask2++) {
            if (__builtin_popcount(mask2) != 2)
                continue;

            bool legal = true;

            for (int i = 0; i < 6; i++) if (mask2 & (1 << i)) {
                if (check(i - 2) && (mask1 & (1 << (i - 2))))
                    legal = false;
                if (check(i + 2) && (mask1 & (1 << (i + 2))))
                    legal = false;
            }

            if (legal) {
                masks.pb((mask1 << 6) + mask2);
            }

        }
    }


    auto T = make_T();
    matrix A(SZ(masks), 1);
    for (int i = 0; i < SZ(masks); i++)
        A.cont[i][0] = 1;


    T = fpow(T, n - 2, 10000);
    A = T * A;
    cout << A() % 10000 << endl;
}

[naive ice]

過了

[jaunty geyser]

@naive ice 該 topcoder 了吧

🛐

[naive ice]

我嘗試過了

但是壓不過

QQ

輸了 40ms

int n, m;
vector<int> masks;

struct matrix {
    vector<vector<int>> cont;

    matrix(const int _n, const int _m) {
        for (int i = 0; i < _n; i++)
            cont.pb(vector<int>(_m, 0));

    }

    matrix(const int _n) {
        for (int i = 0; i < _n; i++)
            cont.pb(vector<int>(_n, 0));
        for (int i = 0; i < _n; i++)
            cont[i][i] = 1;
    }

    matrix operator *(const matrix &_a) {
        matrix res(SZ(cont), SZ(_a.cont[0]));

        for (int i = 0; i < SZ(cont); i++) {
            for (int j = 0; j < SZ(_a.cont[0]); j++) {
                res.cont[i][j] = 0;
                for (int k = 0; k < SZ(_a.cont); k++) {
                    res.cont[i][j] += cont[i][k] * _a.cont[k][j];
                }
                res.cont[i][j] %= P;
            }
        }

        return res;
    }

    void operator %=(const int P) {
        for (auto &col: cont)
            for (auto &it: col)
                it %= P;
    }


    int operator () (){
        int res = 0;
        for (auto &col: cont)
            for (auto &it: col) {
                res += it;
            }
        res %= P; 
        return res;
    }
};

bool check(int i) {
    return (i >= 0 && i < 6);
}

matrix make_T() {
    matrix res(SZ(masks), SZ(masks));

    for (int i = 0; i < SZ(masks); i++) {
        int mask1 = (masks[i] >> 6); // i - 1
        int mask2 = masks[i] & 0b111111; // i
        for (int j = 0; j < SZ(masks); j++) {
            int mask3 = (masks[j] >> 6); // i - 2
            int mask4 = masks[j] & 0b111111; // i - 1

            res.cont[i][j] = (mask4 == mask1);
            

            for (int x = 0; x < 6; x++) if (mask3 & (1 << x)) {
                for (int y = 0; y < 6; y++) if (mask4 & (1 << y)) {
                    for (int z = 0; z < 6; z++) if (mask2 & (1 << z)) {
                        if (abs(x - z) == 1 || abs(x - y) == 2 || abs(y - z) == 2) {
                            res.cont[i][j] = 0;
                            goto fin;
                        }
                    }
                } 
            }
            fin:;
        }
    }
    return res;
}

template<typename T>
T fpow(T a, int b, const int P) {
    T res(SZ(masks));
    
    while (b) {
        if (b % 2) {
            res = res * a;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}

void sol() {
    cin >> n;

    if (n == 1) {
        int ans = 0;
        for (int mask = 0; mask < (1 << 6); mask++)
            ans += __builtin_popcount(mask) == 2;
        cout << ans << endl;
        return;
    }
    
    for (int mask1 = 0; mask1 < (1 << 6); mask1++) {
        if (__builtin_popcount(mask1) != 2)
            continue;
        for (int mask2 = 0; mask2 < (1 << 6); mask2++) {
            if (__builtin_popcount(mask2) != 2)
                continue;

            bool legal = true;

            for (int x = 0; x < 6; x++) if (mask1 & (1 << x)) {
                for (int y = 0; y < 6; y++) if (mask2 & (1 << y)) {
                    if (abs(x - y) == 2)
                        legal = false;
                }
            }

            if (legal) {
                masks.emplace_back((mask1 << 6) + mask2);
            }

        }
    }


    auto T = make_T();
    matrix A(SZ(masks), 1);
    for (int i = 0; i < SZ(masks); i++)
        A.cont[i][0] = 1;

    T = fpow(T, n - 2, 10000);
    A = T * A;

    if (n >= 6) {
        cout << string(4 - to_string(A()).size(), '0');
    }

    cout << A() % 10000 << endl;
}

[ashen storm]

如果我沒記錯的話
矩陣乘法 ikj 常數比較小

[naive ice]

哦好像是