序列递推——cf1204E（好题）

「爱情、让人受尽委屈。」 2023-10-11 09:09 14阅读 0赞

/* 显然用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<<1][N<<1],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<0?x-y+mod:x-y; }
    int main(){
        int n,m;
        scanf("%d%d",&n,&m);
        For(i,0,n+m){ 
            C[i][0]=1;
            For(j,1,i) C[i][j]=add(C[i-1][j],C[i-1][j-1]);
        }   
        For(i,1,m) k[0][i]=1;
        For(i,1,n) For(j,i,m) k[i][j]=add(k[i-1][j],k[i][j-1]);
        For(i,1,n) dp[i][0]=i;
        For(i,1,n)
            For(j,1,m)
                dp[i][j]=add(add(dp[i-1][j],C[i+j-1][j]),mns(dp[i][j-1],mns(C[i+j-1][i],k[i][j-1])));
        cout<<dp[n][m];
    }

转载于:https://www.cnblogs.com/zsben991126/p/11517365.html

发表评论取消回复

表情：

评论列表（有 0 条评论，14人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1204C

CF1204C-Anna, Svyatoslav and Maps 题意： > [题目传送门][Link 1] > 不想说了，阅读题。解法： ...

阳光穿透心脏的1/2处/ 2024年04月20日 10:26/ 0 赞/ 35 阅读

相关 CF1204B

CF1204B-Mislove Has Lost an Array 题意： > 给你n，l，r 表示在区间1-n内至少有l个不相同的数至多有r个不相同的数，...

女爷i/ 2024年04月20日 10:26/ 0 赞/ 30 阅读

相关 CF1204A

CF1204A. BowWow and the Timetable 题意： > 给你一个2进制数，求这个2进制数在10进制中的 $ 4^i $ 的个数。 ...

痛定思痛。/ 2024年04月20日 10:26/ 0 赞/ 37 阅读

相关【Floyd】CF1204 Anna, Svyatoslav and Maps

看错题意了一直看不懂题解浪费了好多时间... ![89d9fb3a0aa3436d85b758035ffeadea.png][]![8abf5d61438e40d099675

梦里梦外;/ 2024年03月22日 11:12/ 0 赞/ 12 阅读

相关【枚举子序列+组合数学+推式子】Cf Edu11 E

[https://codeforces.com/contest/660/problem/E][https_codeforces.com_contest_660_problem_

刺骨的言语ヽ痛彻心扉/ 2024年03月08日 08:21/ 0 赞/ 58 阅读

相关序列递推——cf1204E（好题）

/ 显然用dp[i][j]来表示i个1，j个-1的结果 dp[i][j]由dp[i-1][j]和dp[i][j-1]转移而来即dp[i][j]对应的所有序列，都可以由

「爱情、让人受尽委屈。」/ 2023年10月11日 09:09/ 0 赞/ 15 阅读

相关 CF 570E dp递推

题意：给一个n\m的小写字母地图，找从（1，1）到（n，m）点非升路径，且路径组成的字符串是回文串的路径个数。思路：考虑从两端同时走，然后在中间相遇，走的步数是确定的，

浅浅的花香味﹌/ 2022年05月07日 23:30/ 0 赞/ 131 阅读

相关 Fibonacci序列递归算法与递推（Java）

Fibonacci递推公式： f(1) = f(2) = 1;f(n) = f(n-1)+f(n-2)(n>2).在这里取他除以10007的余数递归 pub

不念不忘少年蓝@/ 2022年04月17日 01:53/ 0 赞/ 143 阅读

相关线性dp——cf1012C好题

比较套路的dp题 / dp[i][j][0|1]:前i座山盖了j座房子，第i座不盖|盖 dp[i][j][0]=min( dp[i-1][j][0]

骑猪看日落/ 2021年12月01日 16:46/ 0 赞/ 210 阅读

相关 cf 1009E

如何看待某cf2000分选手不会一道tag1900的题？难。考虑每段距离的贡献， a\[i\]出现在位置j上，当且仅当j-i休息，并且中间的都不是休息的。

曾经终败给现在/ 2021年10月25日 12:56/ 0 赞/ 229 阅读