【25杭电春季营（2）】 T1007 学计算导致的

Problem Description

你有一个 $n$ 行 $m$ 列的方格，每个格子都填有 0123456789+-* 中的某一个字符。

你从左上角出发，每次可以向右或向下走一格，直到走到右下角。有多少种走法，把经过的所有字符按经过顺序排成一排可以得到一个合法的算式，该算式的得数是 $k$ 的倍数？输出对 $10^9+7$ 求余。

保证左上角、右下角的格子都是数字。称一个算式合法当且仅当没有两个连续的运算符。我们允许数字有前导零，并且此时和 C++ 规则不同，仍把数字看作十进制数。

Input

本题输入有多组测试数据。 输入的第一行有一个正整数 $T（1≤T≤5）$ ，表示数据组数。之后的每一组数据格式如下：

输入的第一行有三个正整数 $n,m,k（2≤n,m≤100，2≤k≤20）$ ，分别表示方格的行数和列数，以及得数的要求。

之后 $n$ 行，每行有 $m$ 个字符，表示这个方格。

Output

输出一行一个自然数，表示符合题意的走法数量对 $10^9+7$ 取余的结果。

Sample Input

1 
3 4 3 
1+07 
4-2* 
22-9

Sample Output

4

Hint

【样例解释】

在给定的网格中，有 $10$ 种可能的走法，得到的算式如下：

• 1+07*9 等于 $64$。
• 1+02*9 等于 $19$。
• 1+02-9 等于 $−6$。
• 1+-???（这类走法有 $3$ 种，均不合法）
• 14-2*9 等于 $−4$。
• 14-2-9（注意有 $2$ 种走法都会得到这个算式，但是算两次）等于 $3$ 。
• 1422-9 等于 $1413$ 。

这 $10$ 种走法中，有 $4$ 种走法对应的算式合法，并且得数是 $3$ 的倍数。

题解

由于在一个不带括号的式子当中，既有加号又有乘号，需要先算乘号。没有办法维护乘法优先进行计算的操作。我们注意到（注意力惊人），一个表达式最终可以化成 $sum+mul \times cur$ 的形式。 $sum$ 表示之前计算到的和， $mul$ 表示当前项的系数， $cur$ 为当前的数。题目中的 $k$ 只有 $20$，$sum,mul,cur$ 均为在 $\mod k$ 意义下的值。可以得到一个 $O(nmk^3)$ 的DP算法，具体转移如下：

• 如果是一个数字 $num$ ，只需要 $cur \gets (10cur+num)$ 。

• 如果是加号，则 $sum \gets sum + mul \times cur,mul \gets 1,cur\gets 0$ 。

• 如果是减号，则 $sum \gets sum + mul \times cur,mul \gets -1,cur\gets 0$ 。

• 如果是乘号，则 $mul \gets (mul\times cur),cur\gets 0$ 。

• 相邻格都是符号则不能转移。

所以，我们只需要枚举一下前面格子的 $sum,mul,cur$ 。由于都是在 $\mod k$ 意义下，可以把 $sum,mul,cur$ 进行状压。我们可以对这个状态的转移建立一个自动机来减少计算次数。

答案就是在 $(n,m)$ 时，满足值为 $0$ 状态的路径数。

代码

const int N = 1e2 + 50;
const int MOD = 1e9 + 7;
int n, m, k;
int st[N][N * 80];
int getid(int sum, int mul, int cur)
{
	return sum * k * k + mul * k + cur;
}
void solve()
{

	cin >> n >> m >> k;
	vector<vector<char>> a(n + 5, vector<char>(m + 5));

	vector<vector<array<int, 8000>>> dp(n + 1, vector<array<int, 8000>>(m + 1, array<int, 8000>{}));

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			cin >> a[i][j];
	int tot = k * k * k;
	for (int sum = 0; sum < k; ++sum)
	{
		for (int mul = 0; mul < k; ++mul)
		{
			for (int cur = 0; cur < k; ++cur)
			{
				for (char num = '0'; num <= '9'; ++num)
				{
					st[num][getid(sum, mul, cur)] = getid(sum, mul, (cur * 10 + num - '0') % k);
				}
				st['+'][getid(sum, mul, cur)] = getid((sum + mul * cur) % k, 1, 0);
				st['-'][getid(sum, mul, cur)] = getid((sum + mul * cur) % k, k - 1, 0);
				st['*'][getid(sum, mul, cur)] = getid(sum, (cur * mul) % k, 0);
			}
		}
	}

	dp[1][1][getid(0, 1, (a[1][1] - '0') % k)] = 1;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			for (int sta = 0; sta < tot; ++sta)
			{
				if (isdigit(a[i][j]) || isdigit(a[i][j - 1]))
					dp[i][j][st[a[i][j]][sta]] = (1ll * dp[i][j][st[a[i][j]][sta]] + dp[i][j - 1][sta]) % MOD;
				if (isdigit(a[i][j]) || isdigit(a[i - 1][j]))
					dp[i][j][st[a[i][j]][sta]] = (1ll * dp[i][j][st[a[i][j]][sta]] + dp[i - 1][j][sta]) % MOD;
			}
		}
	}

	int ans = 0;
	for (int sum = 0; sum < k; ++sum)
	{
		for (int mul = 0; mul < k; ++mul)
		{
			for (int cur = 0; cur < k; ++cur)
			{
				if ((sum + mul * cur) % k == 0)
					ans += dp[n][m][getid(sum, mul, cur)];
				ans %= MOD;
			}
		}
	}
	cout << ans << endl;
}