4051 网格行走

题面

内容

有一个 $n \times m$ 的矩阵 $a$，第 $i$ 行第 $j$ 列有价值为 $a_{i, j}$ 的宝石。现在要从 $(1, 1)$ 走到 $(n, m)$，每一步只能向下或向右走，到一个点必须捡起这个点上的宝石。走到终点后会随机丢弃 $n + m - 1$ 个宝石中的一个宝石，剩下来宝石价值的异或和就是得分。

现在问所有可能情况的得分之和模 $998244353$ 的结果。

输入

输入第一行两个数 $n, m$。

接下来 $n$ 行，每行 $m$ 个数表示 $a_{i, j}$。

输出

输出一行一个数表示得分和模 $998244353$ 的结果。

样例1

输入

2 2
1 2
0 1

输出

8

样例2

输入

10 10
14 7 28 25 21 22 12 3 0 14
21 2 17 15 12 21 5 17 23 26
7 10 17 31 21 14 25 30 28 1
6 4 9 18 20 11 9 5 0 24
20 4 28 23 25 20 3 30 28 5
6 15 18 16 21 31 0 4 5 27
7 2 27 24 15 18 2 30 12 20
6 25 11 18 0 23 13 28 29 3
9 23 3 8 18 21 0 14 13 27
5 3 6 30 22 19 19 29 22 25

输出

14322530

思路

令$f_{i,j,k,0/1}$表示走到$(i,j)$异或和为$k$且还剩$0/1$颗珍珠的方案数。

递推式为：

$f_{i,j,k,0}=f_{i-1,j,k,1}+f_{i,j-1,k,1}+f_{i-1,j,k\oplus{a_{i,j}},0}+f_{i,j-1,{k\oplus{a_{i,j}}},0}$

$f_{i,j,k,1}=f_{i-1,j,{k\oplus{a_{i,j}}},1}+f_{i,j-1,{k\oplus{a_{i,j}}},1}$

最后答案就是$\sum_{k=1}^{127}f_{n,m,k,0}\times{k}$。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int mod=998244353;
const int N=333;
int n,m;//走到i，j位置异或和为k的方案数
int a[N][N],f[N][N][N][2];
int ans;
signed main()
{
    // freopen("E:/下载/Compressed/samples/a3.in","r",stdin);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lld",&a[i][j]);
    f[1][1][a[1][1]][1]=1;
    f[1][1][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(i==1&&j==1) continue;
            for(int k=0;k<=255;k++)
            {
                f[i][j][k][0]=(f[i-1][j][k][1]+f[i][j-1][k][1])%mod+(f[i-1][j][k^a[i][j]][0]+f[i][j-1][k^a[i][j]][0])%mod;
                f[i][j][k][1]=(f[i-1][j][k^a[i][j]][1]+f[i][j-1][k^a[i][j]][1])%mod;
            }
        }
    // for(int k=0;k<=255;k++)
        // printf("f[n][m][%d][0]=%d f[n][m][%d][1]=%d\n",k,f[n][m][k][0],k,f[n][m][k][1]);
            for(int k=0;k<=255;k++)
                ans=(ans+1ll*f[n][m][k][0]*k%mod)%mod;
    cout<<ans%mod;
    return 0;
}