AT2370 Piling Up

https://www.luogu.org/jump/atcoder/2370

题解

答案不是\(2^{2m}\)因为每轮的第一次取球可能会不够。

我们可以设\(dp[i][j]\)表示到了第\(i\)轮，当前白球有\(j\)个的方案数。

转移的话枚举下一次拿球的方案。

白白:\((i,j)->(i+1,j-1)\)

黑黑:\((i,j)->(i+1,j+1)\)

白黑:\((i,j)->(i+1,j)\)

黑白:\((i,j)->(i+1,j)\)

把每个状态放在二维平面上的话，我们其实是在统计本质不同的折线个数。

但是这样会算重。

所以我们需要让每条折线强制碰到底部。

那么我们在状态中记录一下是否碰到底部就行了。

代码

#include<bits/stdc++.h>

#define N 3002

using namespace std;

typedef long long ll;

const int mod=1e9+7;

ll dp[N][N][2];

int n,m;

inline void MOD(ll &x){x=x>=mod?x-mod:x;}

inline ll rd(){

  ll x=0;char c=getchar();bool f=0;

  while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

  return f?-x:x;

}

int main(){

  n=rd();m=rd();

  for(int i=1;i<=n;++i)dp[0][i][0]=1;

  dp[0][0][1]=1;

  for(int i=1;i<=m;++i){

  	for(int j=0;j<=n;++j)

  		for(int k=0;k<2;++k)if(dp[i-1][j][k]){

  		  if(j){

  		  	MOD(dp[i][j-1][k|(j==1)]+=dp[i-1][j][k]);

  		  	MOD(dp[i][j][k|(j==1)]+=dp[i-1][j][k]);

  		  }

          if(j<n){

          	MOD(dp[i][j+1][k]+=dp[i-1][j][k]);

            MOD(dp[i][j][k]+=dp[i-1][j][k]);

          }

  	    }

  }

  ll ans=0;

  for(int i=0;i<=n;++i)MOD(ans+=dp[m][i][1]);

  cout<<ans;

  return 0;

}

巴特西

AT2370 Piling Up

题解

代码

最新文章

热门文章