http://codeforces.com/problemset/problem/256/E

题意：

一个字符串有123构成，给出3*3矩阵代表每个数字之后可以跟的数字。初始全0，代表可以任意取，然后每次操作会改变一个位置。求每次操作后的可行合法字符串方案数。

解析：

首先可以预处理$dp[len][i][j]$表示长度为$len$，以数字i开头，结尾的方案数。

然后动态的维护总答案。例如这样：

前一个和后一个可以用指针和set一起维护。注意当中间位置改变为0时，由于x-0-y不等于(x-0)*(0-y)，所以要删掉当前位置，相当于填入x-y。（当然0-x或者x-0是没关系的）

如果有至少一段的答案为0，那么答案就是0了，0的数量可以用一个变量单独维护。

模数为质数，除法就比较恶心了。因为模数的因子只要4个，所以可以用类似的方法维护这4个因子的次数，剩下的部分用逆元做。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int maxn=1e5+9;
const LL mod=777777777;

int n,m;
int mp[4][4];
LL dp[maxn][4][4];
int l[maxn],r[maxn];
int a[maxn];
set<int>S;
LL Pow(LL a,LL b,LL mod){
    if(a>=mod)a%=mod;
    LL res=1;
    while(b>0){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
LL Ex_gcd(LL a,LL b,LL &x,LL &y){
    if(!b){
        y=0,x=1;
        return a;
    }
    LL ans=Ex_gcd(b,a%b,y,x);
    y-=a/b*x;
    return ans;
}
LL inv(LL a){
    LL x,y;
    Ex_gcd(a,mod,x,y);
    return (x+mod)%mod;
}
//    3*3*7*37*333667
LL ans;
LL sv[5]={0,3,7,37,333667};
int ct[5];
int cnt;
void Mul(LL val){
    if(val==0)cnt++;
    else{
        rep(i,1,4){
            while(val%sv[i]==0){
                val/=sv[i];
                ct[i]++;
            }
        }
        ans=ans*val%mod;
    }
}
void Div(LL val){
    if(val==0)cnt--;
    else{
        rep(i,1,4){
            while(val%sv[i]==0){
                val/=sv[i];
                ct[i]--;
            }
        }
        ans=ans*inv(val)%mod;
    }
}
LL Ans(){
    if(cnt)return 0;
    LL now=ans;
    rep(i,1,4){
        now=now*Pow(sv[i],ct[i],mod)%mod;
    }
    return now;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    rep(i,1,3)rep(j,1,3)cin>>mp[i][j];
    if(n==1){
        rep(i,1,m){
            int p,v;cin>>p>>v;
            if(v==0)cout<<"3\n";
            else cout<<"1\n";
        }
        return 0;
    }
    rep(i,1,3)dp[1][i][i]=1;
    rep(len,2,n){
        rep(i,1,3){
            rep(j,1,3){
                rep(k,1,3){
                    dp[len][i][j]=(dp[len][i][j]+dp[len-1][i][k]*mp[k][j])%mod;
                }
            }
        }
    }
    rep(len,1,n){
        rep(i,1,3){
            rep(j,1,3){
                dp[len][0][0]=(dp[len][0][0]+dp[len][i][j])%mod;
                dp[len][0][i]=(dp[len][0][i]+dp[len][j][i])%mod;
                dp[len][i][0]=(dp[len][i][0]+dp[len][i][j])%mod;
            }
        }
    }
    ans=1;
    Mul(dp[n][0][0]);
    if(!ans)cnt=1;
    l[1]=1;r[1]=n;
    l[n]=1;r[n]=n;
    S.insert(1);
    S.insert(n);
    rep(i,1,m){
        int p,v;cin>>p>>v;
        if(a[p]!=v){
            if(v==0&&p!=1&&p!=n){
                auto it=S.find(p);
                S.erase(it);
                int old=a[p];
                a[p]=0;
                Div(dp[r[p]-p+1][old][a[r[p]]]);
                Div(dp[p-l[p]+1][a[l[p]]][old]);
                Mul(dp[r[p]-l[p]+1][a[l[p]]][a[r[p]]]);
                r[l[p]]=r[p];
                l[r[p]]=l[p];
            }
            else if(S.count(p)){
                auto it=S.find(p);
                int old=a[p];
                a[p]=v;
                if(p<n){
                    Div(dp[r[p]-p+1][old][a[r[p]]]);
                    Mul(dp[r[p]-p+1][v][a[r[p]]]);
                }
                if(p>1){
                    Div(dp[p-l[p]+1][a[l[p]]][old]);
                    Mul(dp[p-l[p]+1][a[l[p]]][v]);
                }
            }
            else{
                auto nex=S.lower_bound(p);
                auto pre=nex;
                pre--;
                int nn=*nex,pp=*pre;
                Div(dp[nn-pp+1][a[pp]][a[nn]]);
                Mul(dp[p-pp+1][a[pp]][v]);
                Mul(dp[nn-p+1][v][a[nn]]);

                a[p]=v;
                l[p]=pp;r[p]=nn;
                l[nn]=p;r[pp]=p;
                S.insert(p);
            }
        }
        cout<<Ans()<<endl;
    }
}