一开始有n个颜色为黑白的球,但不知道黑白色分别有多少,m次操作,每次先拿出一个球,再放入黑白球各一个,再拿出一个球,最后拿出的球按顺序排列会形成一个颜色序列,求颜色序列有多少种
n,m小于等于3000 答案对1e9+7取膜
这个题还是 Power_Leo101 同学教我做的, 自己太弱了,完全不会
这是菊队ppt里推荐的题, 这个学期过了, 学长们就毕业了, 菊队也不再会给我们讲课了
虽然陈菊开学长讲课的画风毒瘤, ppt毒瘤
对于每一次操作,其实是可以看成一次染色的,因为总数总是不变,而颜色却会变化
所以对于每一次染色,即有四种情况: 嘿嘿 黑黑 , 白白, 黑白,白黑
按照常规思路:
我们不妨设 f[i][j] 表示当前进行第i次操作, 还剩下 j 个白球 (其实颜色没影响)
所以对于每一个当前状态则是可以有之前的状态,通过上面列举的四种操作得到
即
if (j>0)
f[i][j] = f[i][j] + f[i-1][j] + f[i-1][j-1]; //是白白和白黑两种情况
if (j<n)
f[i][j] = f[i][j] + f[i-1][j] + f[i-1][j+1]; //是黑白和黑黑两种情况
没想到吧
这是为什么呢???
再通过观察, 可以发现题目要求的是取出的球的不同顺序方案,而在我们的处理中有了很多重复的
因为它要求的只是顺序, 还在序列中的黑白球的数量并不重要!
所以求出所有的方案数之后,我们只需将 n=n-1 再跑一遍
然后用第一次的答案减去第二次的答案,就是真正的答案了. (想想为什么)
#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
#define get getchar()
#define in inline
#define db double
in int read()
{
int t=0; char ch=get;
while(ch<'0' || ch>'9') ch=get;
while (ch<='9' && ch>='0') t=t*10+ch-'0', ch=get;
return t;
}
const int _=3010;
const int mod=1e9+7;
ll n,m,f[_][_];
int main()
{
n=read(),m=read();
for (re int i=0;i<=n;i++)f[0][i]=1;
ll ans=0;
for (re int i=1; i<=m; i++)
for (re int j=0; j<=n; j++)
{
if(j>0)
f[i][j]=(f[i][j]+f[i-1][j-1]+f[i-1][j])%mod;
if(j<n)
f[i][j]=(f[i][j]+f[i-1][j+1]+f[i-1][j])%mod;
}
for (re int i=0; i<=n; i++) ans=(ans+f[m][i])%mod;
ll ans1=0;
memset(f,0,sizeof(f));
for (re int i=0;i<=n-1;i++)f[0][i]=1;
for (re int i=1; i<=m; i++)
for (re int j=0; j<=n-1; j++)
{
if(j>0)
f[i][j]=(f[i][j]+f[i-1][j-1]+f[i-1][j])%mod;
if(j<n-1)
f[i][j]=(f[i][j]+f[i-1][j+1]+f[i-1][j])%mod;
}
for (re int i=0; i<=n-1; i++) ans1=(ans1+f[m][i])%mod;
cout<<((ans-ans1)+mod)%mod;
return 0;
}
嗯, 就这样,这是蒟蒻的第一篇正式题解了
手机扫一扫
移动阅读更方便
你可能感兴趣的文章