题解 P4558 【[JSOI2018]机器人】

· · 题解

吉爷爷题真是做一道不会一道……

趁我还没忘记这题赶紧写一波题解

前置芝士:一个冷静的脑子

嗯做计数题最重要的就是推性质推性质还有推性质

本体题解

首先我们看到这个机器人居然可以遍历整个网格(也就是走出了一个哈密顿回路)就知道这题必然有高论,所以先让我们坐下来推几个结论再说

结论1:属于同一副对角线的两个格子方向必然相同

这里的副对角线指的是下面这张图里数字相同的区域，你会发现属于同一副对角线的元素不一定相邻

但是由于我们机器人的走法是循环的，因此如果我们把这个矩阵复制几份拼在一起你就发现同一副对角线的元素相邻了

那么这是为什么呢?

我们考虑这样一种情况

如果出现了同一副对角线格子方向不同的情况，那么就会出现图中绿色打格子无法被走到的情况，就算绿色的格子是最上角的格子，那么这意味着我们没法回到原点和题意也是不符合的

有了这个结论我们可以推出更强的结论来

结论2:机器人的动作一定是循环的并且循环节为gcd(n,m)

我们发现一件事情，由于一个点左下和右下的元素属于同一对角线，那么我们无论怎么走都会走到同一个对角线上，即使我们穿过边界从n到1或者从m到1也是如此，同一个的对角线上机器人的行为相同因此我们机器人的动作自然就是循环的

那么我们动作的循环节自然就是不循环的副对角线的数目了，看上去应该是max(n,m)不过我们发现其实是gcd(n,m)

证明的话就是把这个矩阵复制几份拼在一起，如果循环节不是gcd(n,m)那么在两个矩形的交界出会出现副对角线颜色不同的情况，而循环节是gcd(n,m)的时候相当于一堆正方形拼在一起自然不会出现问题

结论3:一个行动方案合法当且仅当以下条件成立

假设我们的循环节长度是d,d步中有dx步是向下走,dy步向右走

1.gcd(dx,n)=1 2.gcd(dy,m)=1 3.gcd(dx,d)=1

必要性还是比较显然的,不然根据裴蜀定理我们知道有些坐标永远不可能被表示出来

至于充分性？为啥这样一定有解啊？

我也不知道，nb一点的读者可以自行证明之后告诉我这个菜鸡

dp

好了有了以上三个结论我们现在正式开始做题

那么我们的思路非常暴力，就是枚举之后然后大力dp

为了避开烦人的边界情况(也就是撞上墙之后从另一边绕回来)，我们把矩阵复制3份分别拼在左下角和右上角和右下角，这样我们就避开了分类讨论问题

接下来我们枚举所有合法方案的dx值，显然dx+dy=d所以确定了dx之后dy也唯一确定了

现在我们希望计算所有循环节内走了(dx,dy)步的方案的f(S)之和

好了看起来我们还是没法做，怎么办呢？

我们接着枚举,我们枚举撞车的点坐标和撞车时已经走过了几个循环节

假设我们在(x,y)这个坐标撞车并且在第tim个循环节才撞车

那么我们需要明确一点的是无论我们内部的方案是什么样子的，假设我们在这个循环节开始前位于(x,y)那么在d步行动之后我们必然位于(x+dx,y+dy)这个点上，并且我们经过的点也只能位于(x,y),(x+dx,y+dy)这个矩形中间.

注意这里由于我们把题目中的矩阵额外复制了3份然后把这4个矩阵拼在了一起所以不存在边界问题

那么我们恰好在第tim轮在ax,ay撞车当且仅当我们前tim轮走过的路径都没有撞车,并且前tim-1轮从ax,ay走到x+dx,y+dy的时候都没有撞车

为了解决这个限制问题我们可以把前tim轮走过的矩形区域叠在一起做dp,这样我们只需要设一个dp(i,j)表示从1,1走到i,j中间不经过1的方案数就可以了

我们还要解决前tim-1轮的问题，我们把前tim-1轮走过的矩形区域叠在一起做dp,设一个fdp(i,j)表示从i,j走到(dx+1,dy+1)中间不经过任何1的方案数

假设我们在第tim轮开始时从(sx,sy)这个位置出发,那么我们在sx+a,sy+b撞车的方案数就是

(dp(a-1,b)+dp(a,b-1))fdp(a,b)

当然我们首先保证这个位置是1

意思就是在叠加矩形意义下我们前tim轮走到a,b的路径都没有撞车，前tim-1轮我们走的完整的路径也没有撞车，这样我们就恰好在sx+a,sy+b撞车了

这样我们暴力统计贡献就能算出答案了

复杂度算出来应该是O(Tn^4)但是没有一个n是满的所以不知道除了多少的常数……总之跑的飞快

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=110;typedef long long ll;const ll mod=998244353;
struct mar
{
    int mp[N][N];
    inline int* operator [](const int & x){return mp[x];}
}mp,bas[2];char mde[N][N];
ll dp[N][N];ll fdp[N][N];ll dx;ll dy;ll ans;int n;int m;
inline void solve(mar& p,mar& q,const int& sx,const int& sy,int rd)//两个简单dp 
{
    for(int i=0;i<=dx;i++)
        for(int j=0;j<=dy;j++)p[1+i][1+j]=q[1+i][1+j]|mp[sx+i][sy+j];
    for(int i=1;i<=dx+1;i++)for(int j=1;j<=dy+1;j++)dp[i][j]=0;
    for(int i=1;i<=dx+1;i++)for(int j=1;j<=dy+1;j++)fdp[i][j]=0;
    if(p[1][1]==0)
    {
        dp[1][1]=1;ll v;
        for(int i=1;i<=dx+1;i++)
            for(int j=1;j<=dy+1;j++)
                v=dp[i][j],(dp[i][j+1]+=(!p[i][j+1])*v)%=mod,(dp[i+1][j]+=(!p[i+1][j])*v)%=mod;
    }
    if(q[dx+1][dy+1]==0)
    {
        fdp[dx+1][dy+1]=1;ll v;
        for(int i=dx+1;i>=1;i--)
            for(int j=dy+1;j>=1;j--)
                v=fdp[i][j],(fdp[i][j-1]+=(!q[i][j-1])*v)%=mod,(fdp[i-1][j]+=(!q[i-1][j])*v)%=mod;
    }
    for(int i=1;i<=dx+1;i++)
        for(int j=1;j<=dy+1;j++)
        {
            ll fv;if(p[i][j]==0)continue;
            if(i==1&&j==1)fv=1;else if(i==1)fv=dp[i][j-1];else if(j==1)fv=dp[i-1][j];
            else fv=(dp[i][j-1]+dp[i-1][j])%mod;
            (ans+=(ll)(rd+i+j-2)*fv%mod*fdp[i][j])%=mod;
        }
}
inline int gcd(int a,int b){if(a<b)swap(a,b);while(b){int c=a%b;a=b;b=c;}return a;}
inline void solve()
{
    scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",mde[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)mp[i][j]=(mde[i][j]=='1');
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)mp[i+n][j]=mp[i][j];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)mp[i][j+m]=mp[i][j];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)mp[i+n][j+m]=mp[i][j];int d=gcd(n,m);
    for(dx=0,dy=d;dx<=d;dx++,dy--)//枚举dx和dy 
    {
        if(dx==0&&n!=1)continue;if(dy==0&&m!=1)continue;
        if(gcd(dx,d)!=1||gcd(dx,n)!=1||gcd(dy,m)!=1)continue;
        for(int i=0;i<=dx+1;i++)for(int j=0;j<=dy+1;j++)bas[0][i][j]=0;
        for(int i=0;i<=dx+1;i++)for(int j=0;j<=dy+1;j++)bas[1][i][j]=0;
        for(int rd=0,p=1,q=0;rd<n*m;rd+=d,p^=1,q^=1)
            solve(bas[p],bas[q],(rd*dx/d)%n+1,(rd*dy/d)%m+1,rd);    
    }printf("%lld\n",ans);ans=0;
}
int main(){int T;scanf("%d",&T);for(int z=1;z<=T;z++)solve();return 0;}//拜拜程序~