[dp] Jzoj P5870 地图

news/2024/3/4 9:54:40

Description

Input

Output

Sample Input

4
2 1 1 2

Sample Output

2

Data Constraint

 

 

题解

  • 设f[i][j]为剩下i个1,j个2的地图数量
  • 如果2号用了一条边就是1号点了
  • 根据情况dp

代码

 1 #include <cstdio>
 2 using namespace std;
 3 int n,num[3],f[2010][2010],mo=998244353;
 4 int main()
 5 {
 6     freopen("map.in","r",stdin);freopen("map.out","w",stdout);
 7     scanf("%d",&n);
 8     for (int x,i=1;i<=n;i++) scanf("%d",&x),num[x]++;
 9     f[0][0]=1;
10     for (int i=0;i<=n;i++)
11         for (int x=i;x>=0;x--)
12         {    
13             int y=i-x;
14             if (x>=1&&y==0) (f[x+1][y]+=1ll*f[x-1][y]*x%mo)%=mo;
15             if (x>=2) (f[x][y+1]+=1ll*f[x-2][y]*((1ll*x*(x-1)/2)%mo)%mo)%=mo;
16             if (y>=2) (f[x][y+1]+=1ll*f[x+2][y-2]*((1ll*y*(y-1)/2)%mo)%mo)%=mo;
17             if (i*x) (f[x][y+1]+=1ll*f[x][y-1]*x%mo*y%mo)%=mo;
18         }
19     printf("%d",f[num[1]][num[2]]);
20 }

 

转载于:https://www.cnblogs.com/Comfortable/p/9688483.html


http://www.ppmy.cn/news/264154.html

相关文章

HDU5870 Alice's Adventure in Wonderland

大概做法是这样的 考虑最朴素的做法&#xff0c;预处理出1到所有点的最短路数组dis1和方案数数组cnt1&#xff0c;和预处理出n到所有点的最短路数组dis2和方案数数组出cnt2,然后暴力枚举点对(A,B),如果A和B之间没有连边&#xff0c;那么就可以考虑添加一条正权边&#xff0c;满…

【JZOJ5870】地图

Description 给定N个度数为1或2的点&#xff0c;求所有带标号简单无向图&#xff08;无重边和自环&#xff09;的方案数。 Solution 设度数为2的点有 n n n个&#xff0c;度数为1的有 m m m个。 因为只有1和2&#xff0c;所以图一定是由许多链和大小大于等于3的简单环构成的…

RDA5870调试

时间&#xff1a;20100506 现象&#xff1a;我司准备在MTK6253上换蓝牙芯片为RDA5870. 调试过程&#xff1a; 1、首先将RDA5870给的相关代码放到我们自己的工程中&#xff0c;编译通过。但是在添加的时候要注意用相关的宏名控制。 首先在工程文件中添加&#xff1a; RDA_BLUETO…

mysqldump 逻辑备份的正确姿势

在上一篇文章 MySQL 命令行工具之 mysqldump 深入研究 中&#xff0c;我们搞定了mysqldump的参数和基本原理。那么我们该怎么样最好的使用它的&#xff1f;它有哪些坑呢&#xff1f; 1. 利用mysqldump进行逻辑备份 1&#xff09;全逻辑备份&#xff1a; mysqldump -uxxx -p --f…

AMD OpenCL 大学课程

AMD OpenCL大学课程是非常好的入门级OpenCL教程&#xff0c;通过看教程中的PPT&#xff0c;我们能够很快的了解OpenCL机制以及编程方法。下载地址&#xff1a;http://developer.amd.com/zones/OpenCLZone/universities/Pages/default.aspx 教程中的英文很简单&#xff0c;我相信…

【Linux】软硬链接

文章目录 制作软硬链接&#xff0c;对比差别提出软硬链接的应用场景总结 制作软硬链接&#xff0c;对比差别 制作软链接 1.先创建一个文件&#xff0c;并向其中写入内容&#xff1a; 2.建立软链接&#xff1a;ln -s myfile.txt my-soft 可以发现&#xff0c;软链接是一个独…

tp703n怎么做无线打印服务器,TP-Link TL-WR703N无线路由器无线AP模式怎么设置

TP-Link TL-WR703N无线路由器配置简单&#xff0c;不过对于没有网络基础的用户来说&#xff0c;完成路由器的安装和无线AP模式的设置&#xff0c;仍然有一定的困难&#xff0c;本文学习啦小编主要介绍TP-Link TL-WR703N无线路由器无线AP模式的设置方法! TP-Link TL-WR703N无线路…

TP-Link 886nV6 刷第三方系统回忆

886nV6刷第三方系统 886n普遍只有8m的闪存&#xff0c;刷不了大的第三方系统。因为手头没有闪存就没换&#xff0c;OpenWRT成了优先级最高的系统。相关的刷机教程可去相关论坛查看。 本人在tb购买CH341A编程器使用sop8夹具&#xff0c;夹住flash的引脚进行烧录。 刷机坑的提醒…

tlwr842n服务器无响应,TL-WR842n无线路由器掉线解决方法汇总

《TL-WR842n无线路由器掉线解决方法汇总》由会员分享&#xff0c;可在线阅读&#xff0c;更多相关《TL-WR842n无线路由器掉线解决方法汇总(1页珍藏版)》请在人人文库网上搜索。 1、TL-WR842n无线路由器掉线解决方法汇总用单机接宽带能正常上网的这一台电脑有线连接路由器的LAN口…

tlwr886n发挥最大网速_路由器中的2.4G和5G有什么区别?用错了网速变“龟速”

虽然现在手机流量已经越来越便宜&#xff0c;但是在固定场所&#xff0c;人们还是习惯使用WiFi进行上网。尤其在下载大型文件的时候&#xff0c;WiFi更是必不可少。但是当我们设置或者连接路由器的时候&#xff0c;时常会看到2.4G和5G的信号。那么路由器中&#xff0c;2.4G和5G…

tplink703n无线打印服务器,TP-Link TL-WR703N无线路由器客户端模式(Client)设置上网

越洋帮路由网原创:文章是关于"TP-Link TL-WR703N无线路由器客户端模式(Client)设置上网"的相关知识分享,希望可以帮到大家。 - 素材来源网络 编辑:小易。 TP-Link TL-WR703N迷你无线路由器,在“客户端模式(Client)”下的上网设置方法;TL-WR703N工作在客户端模式(…

TLWR742N路由器服务器无响应,TP-Link TL-WR742N无线路由器怎么设置 | 192路由网

本文介绍了TP-Link TL-WR742N无线路由器的安装、上网设置和无线WiFi设置&#xff0c;TL-WR742N路由器一共有6个硬件版本号&#xff1a;V1.0、V2.0、V3.0、V4.0、V5.0、V6.0&#xff1b;期中V5.0版本在设置上与其它硬件版本有所不同&#xff0c;下文会进行介绍。 步骤一&#xf…

ciscn_2019_s_4-栈迁移

1&#xff0c;三连 程序功能&#xff1a;两次输入 题目类型猜测&#xff1a;栈溢出&#xff0c;栈迁移 2&#xff0c;ida分析 溢出点&#xff1a; system_plt地址: 思路&#xff1a;由于无直接getshell的利用函数&#xff0c;溢出空间只有8字节&#xff08;ebpret占用无法继续…

前端面试:常见的HTML、CSS和JavaScript问题解答

前端开发面试中&#xff0c;HTML、CSS和JavaScript是必考点。以下是常见的HTML、CSS和JavaScript问题的解答&#xff0c;希望能对前端开发者的面试有所帮助。 文档类型&#xff08;doctype&#xff09;的作用是什么&#xff1f; 文档类型用来告诉浏览器当前页面使用哪种HTML标…

在线商城前台开发环境配置

一、项目配置 node 15.14.0 官网下载 https://nodejs.org/zh-cn/download/releases npm 7.7.6 下载node后自动安装npm&#xff0c;如果版本不对就更换对应版本 npm install react7.7.6 下载项目源码 链接&#xff1a;https://www.123pan.com/s/bT07Vv-WICcv.html 解压到一…

c++ 解析html与htmlcxx库

目录 1&#xff0c;htmlcxx Github 版本源码下载 2&#xff0c;htmlcxx Linux 版本源码下载 3&#xff0c;htmlcxx 解析例子 1&#xff0c;htmlcxx Github 版本源码下载 正如在前一篇文章 c CFile 类 里提到的&#xff0c;我想要从指定的 html 文件里提取…

【开发经验】java list.sort的坑

异常信息 Format: Comparison method violates its general contract! Params: null StackTrace: java.lang.IllegalArgumentException: Comparison method violates its general contract! at java.util.TimSort.mergeHi(TimSort.java:899) at java.util.TimSort.mergeAt(TimS…

【水果成篮】

题目描述 你正在探访一家农场&#xff0c;农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示&#xff0c;其中 fruits[i] 是第 i 棵树上的水果 种类 。你想要尽可能多地收集水果。然而&#xff0c;农场的主人设定了一些严格的规矩&#xff0c;你必须按照要求采摘…

持续发挥供应链优势,美菜网助力春节期间餐饮业回春

随着“互联网”时代的不断发展&#xff0c;人们的追求已从“吃饱”变为“吃好”。春节将至&#xff0c;如何做出可口的“年夜饭”&#xff0c;这一看似简单的命题&#xff0c;便成为了餐饮业提升服务质量的关键和竞争的热点。想要做出可口的“年夜饭”&#xff0c;势必需要丰富…

2022年水果市场调查报告分析

中国报告大厅网讯&#xff0c;水果具有丰富的维生素c&#xff0c;是大家在选择营养品的时候会吃的食物&#xff0c;应季水果的营养价值是非常高。以下是对2022年水果市场调查报告分析。 水果产业在国民经济中一直发挥着重要作用。水果市场调查报告分析指出&#xff0c;作为亚洲…
最新文章