抚州建设网站的公司,外贸自己建网站,天津营销网站建设公司排名,阳江网站建设 公司CSP模拟51联测13 B.狗 文章目录 CSP模拟51联测13 B.狗题目大意题目描述输入格式输出格式样例样例 1inputoutput 思路 题目大意
题目描述
小G养了很多狗。
小G一共有 n n n\times n nn 条狗#xff0c;在一个矩阵上。小G想让狗狗交朋友#xff0c;一条狗狗最多只能交一个…CSP模拟51联测13 B.狗 文章目录 CSP模拟51联测13 B.狗题目大意题目描述输入格式输出格式样例样例 1inputoutput 思路 题目大意
题目描述
小G养了很多狗。
小G一共有 n × n n\times n n×n 条狗在一个矩阵上。小G想让狗狗交朋友一条狗狗最多只能交一个朋友不必所有狗狗都有朋友。但是狗狗交朋友有要求具体的第 i i i 行第 j j 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 a_{i,j} ai,j 的喜悦值。一个交友方案的价值就是所有有朋友的狗狗的喜悦值之和。
小G想知道所有交友方案的价值和由于这个数可能很大请对 998244353 998244353 998244353 取模并告诉小G。
朋友关系是双向的,两条狗互相交朋友需要两个d都满足,上下左右不必相邻
上下左右是指正上/正下/正左/正右也就是要在同一行同一列
输入格式
第一行一个整数 n n n。
接下来 n n n 行每行一个长度为 n n n 的字符串第 i i i 行 j j j 列的字符表示 d i , j d_{i,j} di,j。
接下来 n n n 行每行 n n n 个数字第 i i i 行第 j j j 个表示 a i , j a_{i,j} ai,j。
输出格式
一行一个整数表示对 998244353 998244353 998244353 取模的结果。
样例
样例 1
input
4
RRRD
RULL
DULU
URUL
1 2 2 2
1 2 2 1
2 1 2 1
2 2 2 1output
160思路
观察发现 每一行和每一列都是 相互独立 的
我们考虑每一行上 L , R L , R L,R 的的情况
设 f i , j , g i , j f_{i , j},g_{i , j} fi,j,gi,j 分别为前 i i i 个 想选若干个 R R R 还有 j j j 个 R R R 要选的方案数和价值和
1、如果当前不选那么 f i , j f i − 1 , j g i , j g i − 1 , j f_{i , j} f_{i- 1 , j} \newline g_{i , j} g_{i - 1 , j} fi,jfi−1,jgi,jgi−1,j 如果当前是 L L L 并且选那么 f i , j − 1 f i − 1 , j ∗ j g i , j − 1 g i − 1 , j f i − 1 , j ∗ j ∗ a i 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 fi,j−1fi−1,j∗jgi,j−1gi−1,jfi−1,j∗j∗ai 如果当前是 R R R 并且选那么 f i , j 1 f i − 1 , j g i , j 1 g i − 1 , j f i − 1 , j ∗ a i f _{i , j 1} f_{i- 1 , j} \newline g_{i , j 1} g_{i - 1 , j} f_{i - 1 , j} * a_i fi,j1fi−1,jgi,j1gi−1,jfi−1,j∗ai 其实每一列上 U , D U , D U,D 的情况差不多所以最后复杂度 O ( n 3 ) O(n ^3) O(n3)
#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;
}
