hdu 6377 度度熊看球赛 (dp)
2024-09-01 14:03:59
大意: $n$对情侣, $2n$个座位, 对于一个方案, 若$k$对情侣相邻, 则喧闹值增加$D^k$, 求喧闹值期望.
跟CF 840C一样, 设$dp[i][j]$为$i$个人, 有$j$对情侣相邻, 枚举每个人转移即可.
#include <iostream>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll;
const int N = 2e3+10, P = 998244353;
int n, d, dp[N][N], fac[N][N]; int main() {
dp[0][0] = 1;
REP(i,0,2000) REP(j,0,i/2) if (dp[i][j]) {
int &r = dp[i][j];
if (i&1) {
dp[i+1][j] = (dp[i+1][j]+(ll)(i+1-j-2)*r)%P;
dp[i+1][j+1] = (dp[i+1][j+1]+2ll*r)%P;
if (j) dp[i+1][j-1] = (dp[i+1][j-1]+(ll)j*r)%P;
}
else {
dp[i+1][j] = (dp[i+1][j]+(ll)(i+1-j)*r)%P;
if (j) dp[i+1][j-1] = (dp[i+1][j-1]+(ll)j*r)%P;
}
}
REP(i,1,1000) {
fac[i][0] = 1;
REP(j,1,1000) fac[i][j] = (ll)fac[i][j-1]*i%P;
}
while (~scanf("%d%d", &n, &d)) {
int ans = 0;
REP(i,0,n) {
ans = (ans+(ll)dp[2*n][i]*fac[d][i])%P;
}
printf("%d\n", ans);
}
}
最新文章
- Codeforces Round #335 Sorting Railway Cars 动态规划
- .net web获取自己的ip地址
- URAL1355. Bald Spot Revisited
- WF4的数据库 表
- C# using Sendkey function to send a key to another application
- DSP知识
- orace owi介绍
- 给一个int型整数,如何将这个整数的奇偶位互换
- DataGridView绑定数据源
- python基础学习笔记
- [UOJ UR #4追击圣诞老人]
- MVC过滤器处理Session过期
- Linux学习之RPM包管理-yum管理(十七)
- Asp.Net+JQuery.Ajax之$.post
- Socket网络编程--简单Web服务器(4)
- python中的三次握手以及四次挥手
- windows 查看端口
- Shell学习笔记:#*、%*字符串掐头去尾方法
- AngularJS 初始化加载流程
- sql分页使用join提高性能
热门文章
- Python读写Excel文件和正则表达式
- 7.linux磁盘管理 分区 建立文件系统 挂载使用
- MediaPlayer: BufferQueue has been abandoned 解决方案
- delphi 获得父目录–指定级父目录
- RabbitMQ 3.7.X集群:从入门到精通,这一篇就够了
- Eclipse中修改某个java项目的jdk版本【我】
- Spring走向注解驱动编程
- 123457123456#0#-----com.twoapp.jingPinYinYu01----儿童学英语jiemei
- 关于Selenium remote模式分布式执行UI自动化测试必定面临的性能问题
- Tinymce在ASP.NET中的使用方法