具体思路

设 $f_{i,j,k,l}$ 表示放置了 $i$ 个男生，$j$ 个女生，最后一段男生比女生多 $k$ 个，女生比男生多 $l$ 个。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=200,M=25;
const int mod=12345678;
int f[N][N][M][M];
int main(){
	int n,m,K;scanf("%d%d%d",&n,&m,&K);
	f[0][0][0][0]=1;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int k=0;k<=K;k++)
				for(int l=0;l<=K;l++)
					if(f[i][j][k][l]){
						f[i+1][j][k+1][max(l-1,0)]=(f[i+1][j][k+1][max(l-1,0)]+f[i][j][k][l])%mod;
						f[i][j+1][max(k-1,0)][l+1]=(f[i][j+1][max(k-1,0)][l+1]+f[i][j][k][l])%mod;
					}
	int ans=0;
	for(int i=0;i<=K;i++)
		for(int j=0;j<=K;j++)
			ans=(ans+f[n][m][i][j])%mod;
	printf("%d",ans);
	return 0;
}