CF 256E Lucky Arrarys 線段樹+DP

 在w數組中為1。數組初始為0，問有多少種排列方式使數組是Lucky的。並且每次更新之後都要給出總的方案數。

動態規劃可以求相鄰兩個區間合並之後的結果

f(i, j)表示當前區間以i開頭，以j結尾的總方案數。那麼配合更新操作，我們就可以用線段樹來維護。樹中每個節點上面都有一個f數組記錄當前區間的方案數。對於每次更新後的詢問，只需對根節點求和即可。

狀態轉移見代碼。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
#define N 80000
#define Mod 777777777
#define For(i, s, t) for(int i=s; i<=t; i++)
typedef long long ll;
ll f[N<<2][4][4];
int n, m, w[4][4];
void Up(int rt) {
    For(i, 1, 3) For(j, 1, 3) {
        f[rt][i][j] = 0;
        For(p, 1, 3) For(q, 1, 3)
            f[rt][i][j] += w[p][q] ? f[rt<<1][i][p]*f[rt<<1|1][q][j] : 0;
        f[rt][i][j] %= Mod;
    }
}
void build(int L, int R, int rt) {
    if (L == R) {
        For(i, 1, 3) For(j, 1, 3) f[rt][i][j] = (i==j)?1:0;
        return ;
    }
    int Mid = (L + R) >> 1;
    build(L, Mid, rt<<1);
    build(Mid+1, R, rt<<1|1);
    Up(rt);
}
void update(int v, int t, int L, int R, int rt) {
    if (L == R) {
        if (t == 0) {
            For(i, 1, 3) For(j, 1, 3) f[rt][i][j] = (i==j)?1:0;
        } else {
            For(i, 1, 3) f[rt][i][i] = (i==t)?1:0;
        }
        return ;
    }
    int Mid = (L + R) >> 1;
    if (v <= Mid) update(v, t, L, Mid, rt<<1);
    else update(v, t, Mid+1, R, rt<<1|1);
    Up(rt);
}
int main() {
    scanf("%d%d", &n, &m);
    For(i, 1, 3) For(j, 1, 3) scanf("%d", &w[i][j]);
    build(1, n, 1);

    int v, t;
    ll ans = 0;
    while(m--) {
        scanf("%d%d", &v, &t);
        update(v, t, 1, n, 1);
        ans = 0;
        For(i, 1, 3) For(j, 1, 3) ans += f[1][i][j];
        cout << ans % Mod << endl;
    }

    return 0;
}