HDU2276 - Kiki & Little Kiki 2(矩陣快速冪)

HDU2276 - Kiki & Little Kiki 2(矩陣快速冪)

題目鏈接

題意：有n盞燈，編號從1到n。他們繞成一圈，也就是說，1號燈的左邊是n號燈。如果在第t秒的時候，某盞燈左邊的燈是亮著的，那麼就在第t+1秒的時候改變這盞燈的狀態。輸入m和初始燈的狀態。輸出m秒後，所有燈的狀態。

思路：其實每盞燈的狀態之和前一盞和自己有關，所以可以得到一個關系矩陣。假設有6盞燈，因此可以得到關系矩陣如下：
(1, 0, 0, 0, 0, 1)
(1, 1, 0, 0, 0, 0)
(0, 1, 1, 0, 0, 0)
(0, 0, 1, 1, 0, 0)
(0, 0, 0, 1, 1, 0)
(0, 0, 0, 0, 1, 1)
這樣的話就可以以此類推，得到n盞燈時的關系矩陣，然後使用矩陣快速冪進行運算。

PS：在這裡，自己剛開始快速冪是用遞歸的，但是暴棧了。。。後來改成非遞歸才過的。

代碼：

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int MAXN = 105;

struct mat{
    int s[MAXN][MAXN];
    int l;
    mat(int len) {
        memset(s, 0, sizeof(s)); 
        l = len;
    }
    mat operator * (const mat& c) {
        mat ans(l); 
        memset(ans.s, 0, sizeof(ans.s)); 
        for (int i = 0; i < l; i++)
            for (int j = 0; j < l; j++) {
                for (int k = 0; k < l; k++)
                    ans.s[i][j] = (ans.s[i][j] + s[i][k] * c.s[k][j]);
                ans.s[i][j] = ans.s[i][j] % 2;
            }
        return ans;
    }
};

char str[MAXN];
int t;

mat pow_mod(mat c, int k) {
    /*if (k == 1)
        return c; 
    mat a = pow_mod(c, k / 2); 
    mat ans = a * a;
    if (k % 2)
        ans = ans * c;
    return ans;*/
    mat ans = c;
    k--;
    while (k) {
        if (k & 1) 
            ans = ans * c;
        k >>= 1;
        c = c * c;
    }
    return ans;
}

int main() {
    while (scanf("%d", &t) != EOF) {
        scanf("%s", str); 
        int l = strlen(str);
        mat c(l);
        for (int i = 0; i < l; i++)
            for (int j = 0; j < l; j++) {
                if (i == 0) 
                    c.s[i][0] = c.s[i][l - 1] = 1;
                else
                    c.s[i][i - 1] = c.s[i][i] = 1;
            }
        mat tmp(l);
        for (int i = 0; i < l; i++)
            tmp.s[i][0] = str[i] - '0';
        mat ans = pow_mod(c, t);
        ans = ans * tmp;
        for (int i = 0; i < l; i++)
            printf("%d", ans.s[i][0]);
        printf("\n");
    }
    return 0;
}