https://ac.nowcoder.com/acm/contest/330/D

C++版本一

std

题解：

状态压缩，轮廓线DP

好多6x6被骗去写暴搜的.jpg。实际上6x6全是?的答案高达1e18.

解法一：By 野鸡验题人
用 dp[x][state] 表示考虑到第 x 行，该行填写的数字的十进制状态为state的方案数。
这样的复杂度有点大，但是由于题目中的要求和为素数存在很强的限制，因此可以先预处理出所有符合条件的一行的state以及每个state可以转移的状态。加上本题宽松的时限，足以通过。
当然第一维是可以滚动掉的（然而并没有什么卵用）。

解法二：标程
用 dp[x][state] 表示考虑到第 x 个格子，它所在的轮廓线上所有数字的十进制状态为state的方案数。其中state的最高位存它前一行的那一格，最低为存它前一列的那一格。
如图所示，这样状态的转移就是一个“带溢出的十进制左移并补上填的数字“。
当然第一维是可以滚动掉的。

#include <bits/stdc++.h>
using namespace std;
char maze[10][10];
bool isprime[21] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0};
long long dp[1000000 + 7][2];
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%s", maze[i]);
    int top = 1;
    for (int i = 1; i < m; i++)
        top *= 10;
    dp[0][0] = 1;
    int v = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            for (int k = 0; k < top * 10; k++)
            {
                if (dp[k][v])
                {
                    for (int add = 0; add < 10; add++)
                    {
                        if ((maze[i][j] == '?' || maze[i][j] == add + '0') && (!i || isprime[add + k / top]) && (!j || isprime[add + k % 10]))
                        {
                            dp[k % top * 10 + add][v ^ 1] += dp[k][v];
                        }
                    }
                    dp[k][v] = 0;
                }
            }
            v ^= 1;
        }
    }
    long long ans = 0;
    for (int i = 0; i < top * 10; i++)
        ans += dp[i][v];
    printf("%lld\n", ans);
}