序列递推——cf1204E(好题)
2024-09-06 08:05:39
/*
显然用dp[i][j]来表示i个1,j个-1的结果
dp[i][j]由dp[i-1][j]和dp[i][j-1]转移而来
即dp[i][j]对应的所有序列,都可以由dp[i-1][j]在前面加一个1或dp[i][j-1]在前面加一个-1得到,
这里加在前面是因为更容易统计 考虑1加在前面,那么对于任意一种(i-1,j)的排列,贡献都+1,C(i-1+j,j)
考虑-1加在前面,那么对于某些(i,j-1)的排列,贡献-1
考虑哪些不需要,前缀中-1的个数始终大于1的序列本来答案就是0,因此不需要-1 预处理这样的序列个数
f[i][j]表示有i个1,j个-1时,前缀-1数量大于1的序列个数
f[i][j]的来源有两种f[i][j-1],f[i-1][j]
对于f[i][j]的每种序列,都可以由 f[i][j-1] 后加一个-1,或者 f[i-1][j]后面加一个1得到
初始值:f[o][j]=1,f[i][j]=0,i>j
*/
#include <bits/stdc++.h>
#define N 2010
#define mod 998244853
#define For(i,x,y) for(int i=(x);i<=(y);++i)
#define Rof(i,x,y) for(int i=(x);i>=(y);--i)
using namespace std; int C[N<<][N<<],dp[N][N],k[N][N]; inline int add(int x,int y){ return x+y>=mod?x+y-mod:x+y; }
inline int mns(int x,int y){ return x-y<?x-y+mod:x-y; }
int main(){
int n,m;
scanf("%d%d",&n,&m);
For(i,,n+m){
C[i][]=;
For(j,,i) C[i][j]=add(C[i-][j],C[i-][j-]);
}
For(i,,m) k[][i]=;
For(i,,n) For(j,i,m) k[i][j]=add(k[i-][j],k[i][j-]);
For(i,,n) dp[i][]=i;
For(i,,n)
For(j,,m)
dp[i][j]=add(add(dp[i-][j],C[i+j-][j]),mns(dp[i][j-],mns(C[i+j-][i],k[i][j-])));
cout<<dp[n][m];
}
最新文章
- 在Eclipse中,如何把一个java项目变成web项目
- JavaScript控制类名(className属性)
- Java WebClient 总结
- ubuntu16.04安装metasploit+postgresql
- transient的理解
- java 抽象类和接口的区别
- Operating System Concepts with java 项目: Shell Unix 和历史特点
- windows7使用Source insight上远程修改ubuntu共享内核源码
- SQL事务隔离级别
- POJ2763-Housewife Wind(树链剖分)
- Arctic Network
- GIT在windows下搭建
- OpenStack VS Kubernetes,谁是你心中的王者?
- httpclient发送接受请求
- Nginx限制访问次数和并发数
- Exploring Pyramids UVALive - 3516 (记忆化DP)
- poj3436 ACM Computer Factory, 最大流,输出路径
- SSH MVC
- linux :故障提示:Error:No suitable device found: no device found for connection ";System eth0";
- [BZOJ 2186][SDOI 2008] 莎拉公主的困惑