自动搬运

查看原文

来自洛谷，原作者为

	i207M 这个家伙很蠢，什么也没有留下

搬运于2025-08-24 21:39:25，当前版本为作者最后更新于2018-09-01 17:04:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于任意连续的一段，男孩与女孩的数目之差不超过k。求方案数。

n , m ≤ 150，k ≤ 20

这个题我觉得其他题解写的都有问题，状态定义有误

$f[i][j][k][h]$表示放了i个男生，j个女生，所有后缀中，男生减女生的差最大为k，女生减男生的差最大为h的方案数；

转移时枚举下一位放置男生还是女生；

如果这一位放置男生，那么所有前一位的后缀都要加上这个男生，所以男生最大数量会多1，女生会相应减1；

也就是：

(f[i+1][j][k+1][max(h-1,0)]+=tmp)%=md;

如果这一位放女生：

和上一种情况类似，这次女生数量增加，男生数量减少；

(f[i][j+1][max(k-1,0)][h+1]+=tmp)%=md;

注意取模；

注意取max(0)；

其他题解认为这代表任意一段，但是这样无法转移呀

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<bitset>
#include<deque>
#include<ctime>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define ri register int
#define il inline
#define fi first
#define se second
#define mp make_pair
#define pairint pair<int,int>
#define mem0(x) memset((x),0,sizeof (x))
#define mem1(x) memset((x),0x3f,sizeof (x))
il char gc()
{
    static const int BS = 1 << 22;
    static unsigned char buf[BS], *st, *ed;
    if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin);
    return st == ed ? EOF : *st++;
}
#define gc getchar
template<class T>void in(T &x)
{
    x = 0;
    bool f = 0;
    char c = gc();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = 1;
        c = gc();
    }
    while ('0' <= c && c <= '9')
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = gc();
    }
    if (f) x = -x;
}
#undef gc
#define pb push_back
#define int ll
#define md 12345678
int n,m,d;
int f[155][155][22][22];
il int max(const int &a,const int &b)
{
    return a>b?a:b;
}
signed main()
{
#ifdef M207
    freopen("in.in", "r", stdin);
#endif
    in(n),in(m),in(d);
    f[0][0][0][0]=1;
    for(ri i=0;i<=n;++i)
        for(ri j=0;j<=m;++j)
            for(ri k=0;k<=d;++k)
                for(ri h=0;h<=d;++h)
                    if(f[i][j][k][h])
                    {
                        // printf("%lld %lld %lld %lld: %lld\n",i,j,k,h,f[i][j][k][h]);
                        int tmp=f[i][j][k][h];
                        (f[i+1][j][k+1][max(h-1,0)]+=tmp)%=md;
                        (f[i][j+1][max(k-1,0)][h+1]+=tmp)%=md;
                    }
    int ans=0;
    for(ri i=0;i<=d;++i)
        for(ri j=0;j<=d;++j)
            (ans+=f[n][m][i][j])%=md;
    printf("%lld",ans);
    return 0;
}