当前位置: 首页 > news >正文

CSP模拟51联测13 B.狗

CSP模拟51联测13 B.狗

文章目录

  • CSP模拟51联测13 B.狗
    • 题目大意
      • 题目描述
      • 输入格式
      • 输出格式
      • 样例
        • 样例 1
          • input
          • output
    • 思路

题目大意

题目描述

小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 1
output
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,j+=fi1,jgi,j+=gi1,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,j1+=fi1,jjgi,j1+=gi1,j+fi1,jjai
如果当前是 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,j+1+=fi1,jgi,j+1+=gi1,j+fi1,jai
其实每一列上 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;
}
http://www.lryc.cn/news/187682.html

相关文章:

  • GEO生信数据挖掘(七)差异基因分析
  • JAVA-SpringBoot入门Demo用IDEA建立helloworld
  • Unity布料系统Cloth
  • 漏电继电器 LLJ-630F φ100 导轨安装 分体式结构 LLJ-630H(S) AC
  • 数据结构和算法(10):B-树
  • VR会议:远程带看功能,专为沉浸式云洽谈而生
  • 实验室管理系统LIMS
  • 开源ERP和CRM套件Dolibarr
  • 视频号双11激励政策,快来看一看
  • Maven最新版本安装及配置
  • 探索ClickHouse——使用MaterializedPostgreSQL同步PostgreSQL数据库
  • 《向量数据库指南》——向量数据库 有必要走向专业化吗?
  • 你必须知道的数据查询途径!!
  • 火焰原子吸收光谱法、容量法和电感耦合等离子体发射光谱法
  • 亚马逊云科技 2023 柏林峰会主题演讲总结
  • CentOS Stream9 安装远程桌面服务 Xrdp
  • 实施运维01
  • MySQL大表直接复制文件的copy方式
  • Redis-集群
  • 使用CrawlSpider爬取全站数据。
  • 【JUC】Java并发编程从挖坑到入土全解(4-一文讲通LockSupport与线程中断->长图预警)
  • Springboot学习笔记——3
  • jupyter 切换虚拟环境
  • 如何在Apache和Resin环境中实现HTTP到HTTPS的自动跳转:一次全面的探讨与实践
  • 安全防御—密码学
  • 灯具从深圳寄国际物流到墨西哥
  • spark3使用hive zstd压缩格式总结
  • 直线导轨精度等级在设备中有什么影响?
  • windows平台FairMOT的实现
  • 系统架构设计:12 论软件维护方法及其应用