题面

问给\(n\)个男孩和\(m\)个女孩排序，使得对于任意连续一段，男女孩数目之差小于等于\(k\)的方案数。

• \(n,m\leq150,k\leq20\)

  解析

  任意连续一段这个要求好迷啊，不会设状态。。。

那就学习一下。

设男孩为\(1\)，女孩为\(-1\)。

然后我们可以把当前序列的后缀最大值和后缀最小值加入状态。

于是就成了，设\(f[i][j][k][l]\)表示到第\(i\)个人，排了\(j\)个男孩，后缀最大值为\(k\)，最小值为\(-l\)的方案数。

\(k\)和\(l\)都不会到负数，具体可参考最大子段和的贪心思想。

复杂度\(O(n^2k^2)\)，空间要卡着开。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define re register#define il inline#define fp(i,a,b) for(re int i=a;i<=b;++i)#define fq(i,a,b) for(re int i=a;i>=b;--i)using namespace std;const int mod=12345678;int n,m,K,f[22][22][152][302],ans;il ll gi(){ re ll x=0,t=1; re char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t;}il void add(re int &x,re int y){x+=y;if(x>=mod) x-=mod;}int main(){ n=gi();m=gi();K=gi(); f[0][0][0][0]=1; fp(i,1,n+m) fp(j,0,min(i,n)) fp(k,0,K) fp(l,0,K) { if(!f[k][l][j][i-1]) continue; if(j