CSP模拟51联测13 B.狗
目录题目大意
题目描述
小G养了很多狗。
小G一共有 \(n\times n\) 条狗，在一个矩阵上。小G想让狗狗交朋友，一条狗狗最多只能交一个朋友，不必所有狗狗都有朋友。但是狗狗交朋友有要求，具体的，第 \(i\) 行第 \(j\) 列的狗有两个值 \(d_{i,j}\in\{\texttt{U},\texttt{D},\texttt{L},\texttt{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
output
160
思路
观察发现 每一行和每一列都是 相互独立 的
我们考虑每一行上 \(L , R\) 的的情况
设 \(f_{i , j},g_{i , j}\) 分别为前 \(i\) 个 ，想选若干个 \(R\) ，还有 \(j\) 个 \(R\) 要选的方案数和价值和
1、如果当前不选那么：
\[f_{i , j} += f_{i- 1 , j} \newline g_{i , j} += g_{i - 1 , j} \]如果当前是 \(L\) 并且选那么：
\[f_{i , j - 1} += f_{i - 1 , j } * j \newline g_{i , j - 1} += g_{i - 1 , j} + f_{i - 1 , j} * j * a_i \]如果当前是 \(R\) 并且选那么 ：
\[f _{i , j + 1} += f_{i- 1 , j} \newline g_{i , j + 1} += g_{i - 1 , j} + f_{i - 1 , j} * a_i \]其实每一列上 \(U , D\) 的情况差不多，所以最后复杂度 \(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;
}