邢台做网站的公司,西安市建设网,宝塔配置wordpress,网页设计代码模板html静态正题
题目链接:https://www.luogu.com.cn/problem/AT2370 题目大意
有nnn个黑白球#xff0c;但是具体颜色个数不确定#xff0c;进行mmm次操作#xff1a;拿出一个球然后放入黑白球各一个#xff0c;再拿出一个球。
求最后颜色序列的种类数。 1≤n,m≤30001\leq n,m\le…正题
题目链接:https://www.luogu.com.cn/problem/AT2370 题目大意
有nnn个黑白球但是具体颜色个数不确定进行mmm次操作拿出一个球然后放入黑白球各一个再拿出一个球。
求最后颜色序列的种类数。
1≤n,m≤30001\leq n,m\leq 30001≤n,m≤3000 解题思路
如果开始的颜色确定那么有个很显然的dpdpdp设fi,jf_{i,j}fi,j表示进行了iii次操作还有jjj个白球的方案。但是如果开始的不确定我们可能会导致大量的算重。
考虑怎么解决掉算重问题的话对于一种取出方案假设白球最多减少了xxx我们就把它计入开始白球有xxx个的方案里也就是当且仅当这个时候存在一个时刻白球个数为000。
所以多开一维记一下白球有没有到过000就好了。
时间复杂度O(nm)O(nm)O(nm) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N3100,P1e97;
int n,m,f[N][N][2];
int main()
{scanf(%d%d,n,m);for(int i1;in;i)f[0][i][0]1;f[0][0][1]1;for(int i1;im;i){for(int j0;jn;j){if(j0){(f[i][j-1][1]f[i-1][j][1])%P;(f[i][j][1]f[i-1][j][1])%P;if(j1)(f[i][j-1][1]f[i-1][j][0])%P;else (f[i][j-1][0]f[i-1][j][0])%P;if(j1)(f[i][j][1]f[i-1][j][0])%P;else (f[i][j][0]f[i-1][j][0])%P;}if(jn){(f[i][j1][1]f[i-1][j][1])%P;(f[i][j][1]f[i-1][j][1])%P;(f[i][j1][0]f[i-1][j][0])%P;(f[i][j][0]f[i-1][j][0])%P;}}}int ans0;for(int i0;in;i)(ansf[m][i][1])%P;printf(%d\n,ans);return 0;
}
