P4558 [JSOI2018]机器人 结论&DP

吉爷爷可真是一位神仙...
看到题目毫无思路，发现题目限制和条件较多，让我们先坐下来数一数条件，推一推结论。
机器人行走要求：
1.机器人只能向右或向下。
2.机器人走到边界后会回到行/列坐标为1的地方。
3.要求机器人走过每一个点且仅走一次。
4.是先规定好了机器人的每一种行走路线，再放的障碍物。

1.从左下到右上直线上机器人的行走方向相同。

这是最基本的一条结论，我们观察一下对于 \((i+1,j)\) 和 \((i,j+1)\) 这两个点，倘若在这两个点走的方向不一样，那么 \((i+1,j+1)\) 这个点要么走不到，要么会走两遍，都不符合题意。

2.机器人行动的循环节是 \(gcd(n,m)\) 。

我们从左下向右上画出每一条对角线（注意还有右下角），一共有\(n+m\)条，将方向一样的用一种颜色涂上，一种颜色会涂 \(\displaystyle \frac{lcm(n+m,n)}{n}\) 条线，一共就需要 \(\displaystyle \frac {n+m} { \frac{lcm(n+m,n)}{n}}=gcd(n,m)\) 种颜色，也就是循环节的长度。

3.设在一个循环节里机器人向下走了 \(dx\) 步，向右走了 \(dy\) 步，机器人的行走方案合法当且仅当 \(gcd(dx,n)=1,gcd(dy,m)=1,gcd(dx,dy)=1\) 。

前两个用裴蜀定理很好解释，对于第三个，我们设 \(d=gcd(n,m)\) ,那么 \(dx+dy=d\) ,因为 \(gcd(dx,n)=1\) ,所以 \(gcd(dx,d)=1\) ,所以 \(gcd(dx,dy)=1\) 。
因为 \(n\) 比较小，暴力枚举一下 \(dx\) 就行啦。
DP设 \(val[x][y]\) 为按照 \(dx,dy\) 走，最早什么时候撞上障碍物，含义就是只要经过了 \((x,y)\) ，那么在第 \(val[x][y]\) 步一定会撞上障碍物。
设 \(f[i][j][k]\) 为从起点到 \((i,j)\) 的所有路径中，路上最小的 \(val\) 是 \(k\) 的方案数，因为我们确定了前 \(d\) 步整张地图的行走方案就确定下来了，所以我们只用DP到 \((dx+1,dy+1)\) (注意我们的起点是 \((1,1)\) ).最后求一下方案数*val之和就行了。

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
int T, n, m, d, ans, x, y;
const int N = 52, mod = 998244353;
int val[N][N], f[N][N][N * N];
char mp[N][N];
int work(int x) {return x >= mod ? x - mod : x;}
int GCD(int x, int y) {return y ? GCD(y, x % y) : x;}
int DP(int dx, int dy) 
{
    for (int i = 1; i <= dx + 1; ++i)
        for (int j = 1; j <= dy + 1; ++j)
            for (int k = 1; k <= n * m; ++k)f[i][j][k] = 0;
    f[1][1][val[1][1]] = 1;
    for (int i = 1; i <= dx + 1; ++i)
        for (int j = 1; j <= dy + 1; ++j)
            for (int k = 1; k <= n * m; ++k) 
            {
                if (!f[i][j][k])continue;
                int &t1 = f[i + 1][j][min(k, val[i + 1][j])], &t2 = f[i][j + 1][min(k, val[i][j + 1])];
                if (i <= dx)t1 = work(t1 + f[i][j][k]);
                if (j <= dy)t2 = work(t2 + f[i][j][k]);
            }
    int res = 0;
    for (int i = 1; i <= n * m; ++i)res = work(res + (LL)i * f[dx + 1][dy + 1][i] % mod);
    return res;
}
int main() 
{
    cin >> T;
    while (T--) 
    {
        scanf("%d%d", &n, &m); d = GCD(n, m); ans = 0;
        for (int i = 1; i <= n; ++i)scanf("%s", mp[i] + 1);
        for (int dx = 0, dy; dx <= d; ++dx) 
        {
            dy = d - dx;
            if (GCD(dx, dy) != 1 || GCD(dx, n) != 1 || GCD(dy, m) != 1)continue;
            for (int x = 1; x <= dx + 1; ++x)
                for (int y = 1; y <= dy + 1; ++y) 
                {
                    int tx = x, ty = y, w = x + y - 2; val[x][y] = n * m;
                    do 
                    {
                        if (mp[tx][ty] == '1') {val[x][y] = w; break;}
                        tx += dx, ty += dy, w += d;
                        if (tx > n)tx -= n; if (ty > m)ty -= m;
                    } while (tx != x || ty != y);
                }
            ans = work(ans + DP(dx, dy));
        }
        cout << ans << "\n";
    }
    return 0;
}