设f(i,j)f(i,j)为走到(i,j)(i,j)的方案数,且第ii行里包含点(i,j)(i,j)的区间为[l,r][l,r],则有f(i,j)=∑rk=lf(i−1,k)f(i,j)=∑k=lrf(i−1,k),这里的kk就代表着从前一行的第kk列走下来。可以发现这个转移方程可以转换成一个矩阵形式,即(f(i,1),f(i,2),…,f(i,m))=(f(i−1,1),f(i−1,2),…,f(i−1,m))⋅A(f(i,1),f(i,2),…,f(i,m))=(f(i−1,1),f(i−1,2),…,f(i−1,m))⋅A其中AA为状态转移矩阵。求从第i−1i−1行到第ii行的转移矩阵是可以用O(m2)O(m2)的时间复杂度来实现的。而最后一行的答案就是第一行的状态矩阵乘上这nn行转移矩阵的乘积。在本题中,由于给出了起点和终点,所以若设这nn行转移矩阵的乘积为A,则答案就是A(a,b)A(a,b)。用线段树维护每行的矩阵以及区间的矩阵乘积即可。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 50005;
const int mod = 1e9 + 7;

int n, m, q;
char c[MAXN][12];
int a[MAXN][12];

struct Mat {
    int m[12][12];
} st[MAXN << 2];

#define lson (p << 1)
#define rson (p << 1 | 1)
#define mid ((l + r) >> 1)

int add(int a, int b)
{
    return a + b >= mod ? a + b - mod : a + b;
}

int mul(ll a, int b)
{
    return a * b >= mod ? a * b % mod : a * b;
}
void print(Mat a){
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            cout<<a.m[i][j]<<" ";
        }
        cout<<endl;
    }
}
Mat Mmul(Mat a, Mat b)
{
    Mat c;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++) {
            c.m[i][j] = 0;
            for (int k = 1; k <= m; k++)
                c.m[i][j] = add(c.m[i][j], mul(a.m[i][k], b.m[k][j]));
        }
    return c;
}

void Mupd(int p, int x)
{
    memset(st[p].m, 0, sizeof(st[p].m));
    for (int i = 1; i <= m; i++)
        if (!a[x][i]) {
            st[p].m[i][i] = 1;
            for (int j = i - 1; j >= 1 && !a[x][j]; j--)
                st[p].m[j][i] = 1;
            for (int j = i + 1; j <= m && !a[x][j]; j++)
                st[p].m[j][i] = 1;
        }
}

void build(int p, int l, int r)
{
    if (l == r) {
        Mupd(p, l);
        return;
    }
    build(lson, l, mid);
    build(rson, mid + 1, r);
    st[p] = Mmul(st[lson], st[rson]);
    // cout<<"**********************"<<endl;
    // cout<<p<<" "<<endl;
    // print(st[p]);
    // cout<<"**********************"<<endl;
}

void upd(int p, int x, int y, int l, int r)
{
    if (l == r) {
        Mupd(p, l);
        return;
    }
    if (x <= mid)
        upd(lson, x, y, l, mid);
    else
        upd(rson, x, y, mid + 1, r);
    st[p] = Mmul(st[lson], st[rson]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%s", c[i] + 1);
        for (int j = 1; j <= m; j++)
            a[i][j] = c[i][j] - '0';
    }
    build(1, 1, n);
    while (q--) {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if (op == 1) {
            a[x][y] ^= 1;
            upd(1, x, y, 1, n);
        } else
            printf("%d\n", st[1].m[x][y]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注