CSP模擬51聯(lián)測(cè)13 B.狗

題目大意

題目描述

小G養(yǎng)了很多狗。

小G一共有 $n\times n$ 條狗，在一個(gè)矩陣上。小G想讓狗狗交朋友，一條狗狗最多只能交一個(gè)朋友，不必所有狗狗都有朋友。但是狗狗交朋友有要求，具體的，第 $i$ 行第 $j$ 列的狗有兩個(gè)值 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è)交友方案的價(jià)值就是所有有朋友的狗狗的喜悅值之和。

小G想知道所有交友方案的價(jià)值和，由于這個(gè)數(shù)可能很大，請(qǐng)對(duì) $998244353$ 取模并告訴小G。

朋友關(guān)系是雙向的,兩條狗互相交朋友需要兩個(gè)d都滿足,上下左右不必相鄰

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

輸入格式

第一行一個(gè)整數(shù) $n$。

接下來(lái) $n$ 行每行一個(gè)長(zhǎng)度為 $n$ 的字符串，第 $i$ 行 $j$ 列的字符表示 $d_{i,j}$。

接下來(lái) $n$ 行每行 $n$ 個(gè)數(shù)字，第 $i$ 行第 $j$ 個(gè)表示 $a_{i,j}$。

輸出格式

一行一個(gè)整數(shù)表示對(duì) $998244353$ 取模的結(jié)果。

樣例

樣例 1

input

4
RRRD
RULL
DULU
URUL
1 2 2 2 
1 2 2 1 
2 1 2 1 
2 2 2 1

output

160

思路

觀察發(fā)現(xiàn) 每一行和每一列都是 相互獨(dú)立 的

我們考慮每一行上 $L,R$ 的的情況

設(shè) $f_{i,j},g_{i,j}$ 分別為前 $i$ 個(gè) ，想選若干個(gè) $R$ ，還有 $j$ 個(gè) $R$ 要選的方案數(shù)和價(jià)值和

1、如果當(dāng)前不選那么：
$$\begin{gathered} f_{i,j}+=f_{i?1,j} \\ {g}_{i,j}+=g_{i?1,j} \end{gathered}$$
如果當(dāng)前是 $L$ 并且選那么：
$$\begin{gathered} f_{i,j?1}+=f_{i?1,j}?j \\ {g}_{i,j?1}+=g_{i?1,j}+f_{i?1,j}?j?a_i \end{gathered}$$
如果當(dāng)前是 $R$ 并且選那么 ：
$$\begin{gathered} f_{i,j+1}+=f_{i?1,j} \\ {g}_{i,j+1}+=g_{i?1,j}+f_{i?1,j}?a_i \end{gathered}$$
其實(shí)每一列上 $U,D$ 的情況差不多，所以最后復(fù)雜度 $O(n^3)$

#include <bits/stdc++.h>
#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;
}