ABC228G Digits on Grid 做题记录

给定一个 $H\times W$ 的矩阵 $c$ 和一个整数 $n$。

起初在任意格子上放置一个棋子，接下来操作 $n$ 次，第 $i$ 次操作：

• 若 $i$ 是奇数，则把棋子移动到当前所在行中任意一个格子（可以不动）；
• 若 $i$ 是偶数，则把棋子移动到当前所在列中任意一个格子（可以不动）；

把每次操作完后棋子所在的格子上的数依次写下，形成一个长度为 $2n$ 的序列 $b$，请你求出有多少种可能的序列 $b$，对 $998244353$ 取模。

$1\le H,W\leq10$，$1\le n\leq 300$，$1\le c_{i,j}\le 9$。

发现奇数次操作之前不关心所在列，偶数次操作之前不关心所在行，那么一个朴素的想法是设 $f_{i,j}$ 表示第 $i$ 次操作完后在第 $j$ 行/列的答案。

但是由于有可能有数字重复的格子，所以可能会算重。

观察到一个性质：设 $f(b)$ 为所有能形成 $b$ 的路径的末尾位置的集合，那么两个 $b$ 相同当且仅当 $f(b)$ 相同。

证明是显然的。

那么设 $f_{i,S}$ 表示第 $i$ 次操作完了后 $f(b)=S$（只保留行或列）的答案。

转移是显然的，时间复杂度 $O(n(2^H+2^W)HW)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=15,BS=1<<10,KS=605,p=998244353;

int n,m,k;
int a[S][S];
int f[KS][BS];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	k*=2;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf(" %c",&a[i][j]),a[i][j]-='0';
	int nl=1<<n,ml=1<<m;
	f[0][nl-1]=1;
	for(int i=0;i<=k-1;i++)
	{
		if(i&1^1)
		{
			for(int j=1;j<nl;j++)
			{
				for(int v=1;v<=9;v++)
				{
					int nv=0;
					for(int x=1;x<=n;x++)
					{
						if(j>>x-1&1^1) continue;
						for(int y=1;y<=m;y++) if(a[x][y]==v) nv|=1<<y-1;
					}
					add(f[i+1][nv],f[i][j]);
				}
			}
		}
		else
		{
			for(int j=1;j<ml;j++)
			{
				for(int v=1;v<=9;v++)
				{
					int nv=0;
					for(int y=1;y<=m;y++)
					{
						if(j>>y-1&1^1) continue;
						for(int x=1;x<=n;x++) if(a[x][y]==v) nv|=1<<x-1;
					}
					add(f[i+1][nv],f[i][j]);
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<nl;i++) add(ans,f[k][i]);
	printf("%d\n",ans);
	return 0;
}