CSP模拟51联测13 B.狗

CSP模拟51联测13 B.狗

题目大意

题目描述

小G养了很多狗。

小G一共有 $n\times n$ 条狗，在一个矩阵上。小G想让狗狗交朋友，一条狗狗最多只能交一个朋友，不必所有狗狗都有朋友。但是狗狗交朋友有要求，具体的，第 $i$ 行第 $j$ 列的狗有两个值 d i , j ∈ { U , D , L , R } d_{i,j}\in\{\texttt{U},\texttt{D},\texttt{L},\texttt{R}\} di,j​∈{U,D,L,R} 表示它只能和上/下/左/右的狗狗交朋友，如果成功交友能得到 $a_{i,j}$ 的喜悦值。一个交友方案的价值就是所有有朋友的狗狗的喜悦值之和。

小G想知道所有交友方案的价值和，由于这个数可能很大，请对 $998244353$ 取模并告诉小G。

朋友关系是双向的,两条狗互相交朋友需要两个d都满足,上下左右不必相邻

上下左右是指正上/正下/正左/正右，也就是要在同一行同一列

输入格式

第一行一个整数 $n$。

接下来 $n$ 行每行一个长度为 $n$ 的字符串，第 $i$ 行 $j$ 列的字符表示 $d_{i,j}$。

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

输出格式

一行一个整数表示对 $998244353$ 取模的结果。

样例

样例 1

input

4
RRRD
RULL
DULU
URUL
1 2 2 2 
1 2 2 1 
2 1 2 1 
2 2 2 1
1
2
3
4
5
6
7
8
9

output

160
1

思路

观察发现 每一行和每一列都是 相互独立 的

我们考虑每一行上 $L,R$ 的的情况

设 $f_{i,j},g_{i,j}$ 分别为前 $i$ 个 ，想选若干个 $R$ ，还有 $j$ 个 $R$ 要选的方案数和价值和

1、如果当前不选那么：
$$\begin{gathered} f_{i,j}+=f_{i-1,j} \\ {g}_{i,j}+=g_{i-1,j} \end{gathered}$$
如果当前是 $L$ 并且选那么：
$$\begin{gathered} f_{i,j-1}+=f_{i-1,j}\ast j \\ {g}_{i,j-1}+=g_{i-1,j}+f_{i-1,j}\ast j\ast a_i \end{gathered}$$
如果当前是 $R$ 并且选那么 ：
$$\begin{gathered} f_{i,j+1}+=f_{i-1,j} \\ {g}_{i,j+1}+=g_{i-1,j}+f_{i-1,j}\ast a_i \end{gathered}$$
其实每一列上 $U,D$ 的情况差不多，所以最后复杂度 $O(n^3)$

#include 
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define LL long long
using namespace std;
const LL mod = 998244353;
const int N = 505;
int n , m , cnt , flg[N];
LL f[N][N] , g[N][N] , p[N << 1] , q[N << 1] , mp[N][N] , a[N];
char s[N][N];
void solve () {
    memset (f , 0 , sizeof (f));
    memset (g , 0 , sizeof (g));
    f[0][0] = 1;
    fu (i , 1 , m) {
        fu (j , 0 , m) {
            f[i][j] = (f[i][j] + f[i - 1][j]) % mod;
            g[i][j] = (g[i][j] + g[i - 1][j]) % mod;
            if (!flg[i]) {
                f[i][j - 1] = (f[i][j - 1] + f[i - 1][j] * j % mod) % mod;
                g[i][j - 1] = (g[i][j - 1] + (g[i - 1][j] * j % mod + f[i - 1][j] * j % mod * a[i] % mod) % mod) % mod;
            }
            else {
                f[i][j + 1] = (f[i][j + 1] + f[i - 1][j]) % mod;
                g[i][j + 1] = ((g[i][j + 1] + g[i - 1][j]) % mod + f[i - 1][j] * a[i] % mod) % mod;
            }
        }
    }
    p[++cnt] = g[m][0];
    q[cnt] = f[m][0];
}
int main () {
    char c;
    scanf ("%d" , &n);
    fu (i , 1 , n) {
        fu (j , 1 , n) {
            c = getchar ();
            while (c != 'U' && c != 'D' && c != 'L' && c != 'R') c = getchar ();
            s[i][j] = c;
        }
    }
    fu (i , 1 , n)
        fu (j , 1 , n) 
            scanf ("%lld" , &mp[i][j]);
    fu (i , 1 , n) {
        m = 0;
        fu (j , 1 , n) {
            if (s[i][j] == 'L' || s[i][j] == 'R') {
                flg[++m] = (s[i][j] == 'R');
                a[m] = mp[i][j];
            }
        }
        if (m) solve ();
    }
    fu (i , 1 , n) {
        m = 0;
        fu (j , 1 , n) {
            if (s[j][i] == 'U' || s[j][i] == 'D') {
                flg[++m] = (s[j][i] == 'D');
                a[m] = mp[j][i];
            }
        }
        if (m) solve ();
    }
    LL k , ans = 0;
    fu (i , 1 , cnt) {
        k = p[i];
        fu (j , 1 , cnt) {
            if (i != j)
                k = (k * q[j]) % mod;
        }
        ans = (ans + k) % mod;
    }
    // printf ("%lld" , ans);
    cout << q[3] << " " << p[3];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76