「Codeforces 593E」Strange Calculation and Cats

发表于 | | 阅读次数:
字数统计: 952 字

Description

题目链接：Codeforces 593E

Gosha 的宇宙是一个由 $n$ 行 $m$ 列组成的表格。他经常被邀请去某个地方，每次接到邀请后，他会先计算到达那个地方的路径方案数，然后再动身出发。Gosha 的房子位于 $(1,1)$。

在任何时刻，Gosha 都会从当前格子到达相邻的格子，当然不会超出边界。此外，他也可以选择不移动而停留在当前格子里。

他除了喜欢奇怪的计算，还对猫过敏，因此他从来不去有猫的格子。Gosha 清楚地知道他何时何地会被邀请，也知道猫的在格子上的行程。形式化地讲，他有 $q$ 条记录，第 $i$ 条记录为如下形式之一：

  • 1 x y t：Gosha 在时刻 $t​$ 被邀请去格子 $(x,y)​$。保证在当前时刻 $(x,y)​$ 是没有猫的。
  • 2 x y z：有一只猫会在时刻 $t$ 来到格子 $(x,y)$。保证在当前时刻 $(x,y)$ 是没有别的猫的。
  • 3 x y z：有一只猫会在时刻 $t$ 离开格子 $(x,y)$。保证在当前时刻 $(x,y)$ 是有猫的。

Gosha 需要你计算出对于每个邀请 $i$，他在时刻 $t_i$ 到达格子 $(x_i,y_i)$ 的方案数。假设他在时刻 $1$ 时从格子 $(1,1)$ 开始移动。

注意：Gosha 在移动过程中，可以多次访问同一个点，包括 $(1,1)$ 和 $(x_i,y_i)$。由于方案数过大，请将它对 $10^9+7$ 取模。

数据范围：$1\le n\cdot m\le 20$，$1\le q\le 10^4$，$1\le x_i\le n$，$1\le y_i\le m$，$2\le t_i<t_{i+1}\le 10^9$

Solution

我们把这个 $n\times m$ 的矩阵压缩成一维的，定义 $f_i$ 表示走到 $i$ 格子的方案数。对于当前情况构造转移矩阵 $A$。$A_{i,j}$ 的值为 $1$ 当且仅当可以从 $i$ 走到 $j$。由于时间 $t_i$ 是递增的，直接矩阵快速幂求出答案即可。

注意：当某个点的状态改变（操作 $2​$ 或 $3​$）时，应该把它的 $f​$ 值设为 $0​$！

时间复杂度：$O(nmq+(nm)^3\log t_i)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=25;
const int mod=1e9+7;
const int dx[]={1,-1,0,0,0},dy[]={0,0,1,-1,0};
int h,w,n,q;
bool ok[N][N];

void upd(int &x,int y) {
    (x+=y)>=mod&&(x-=mod);
}
struct Matrix {
    int n,m,A[N][N];
    Matrix(int _n=0,int _m=0) {
        n=_n,m=_m,memset(A,0,sizeof(A));
    }
    void operator ~ () {
        for(int i=1;i<=n;++i) A[i][i]=1;
    }
    Matrix operator * (const Matrix &b)const {
        Matrix ans(n,b.m);
        for(int i=1;i<=n;++i) for(int j=1;j<=b.m;++j) for(int k=1;k<=m;++k) {
            upd(ans.A[i][j],1LL*A[i][k]*b.A[k][j]%mod);
        }
        return ans;
    }
    Matrix operator ^ (const int &b)const {
        Matrix ans(n,n),x=*this; ~ans;
        for(int p=b;p;p>>=1,x=x*x) if(p&1) ans=ans*x;
        return ans;
    }
};
void build(Matrix &a) {
    memset(a.A,0,sizeof(a.A));
    for(int i=1;i<=h;++i) for(int j=1;j<=w;++j) if(ok[i][j]) {
        for(int k=0;k<=4;++k) {
            int x=i+dx[k],y=j+dy[k];
            if(x>=1&&x<=h&&y>=1&&y<=w&&ok[x][y]) a.A[(i-1)*w+j][(x-1)*w+y]=1;
        }
    }
}
int main() {
    scanf("%d%d%d",&h,&w,&q),n=h*w;
    int now=1;
    Matrix ans(n,1),a(n,n);
    ans.A[1][1]=1;
    memset(ok,1,sizeof(ok));
    while(q--) {
        int opt,x,y,t;
        scanf("%d%d%d%d",&opt,&x,&y,&t);
        build(a),ans=(a^(t-now))*ans,now=t;
        if(opt==1) printf("%d\n",ans.A[(x-1)*w+y][1]);
        if(opt==2) ans.A[(x-1)*w+y][1]=0,ok[x][y]=0;
        if(opt==3) ans.A[(x-1)*w+y][1]=0,ok[x][y]=1;
    }
    return 0;
}
0%