$O(nk^2)$题解

发现放公牛和母牛可以转化成在一张网格图上走，如果放公牛就沿 x 走，放母牛就沿 y 走。

然后他有一个限制，就是任何时候的差的绝对值不能超过 k，所以可以在网格图上画两条线，只要不越过线就行了。

然后枚举下面线的截距，假设他为a，那么上面截距就是k-a。

然后你dp的时候注意能不能转移就行了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,p,ans,facn,facm,dp[1005][1005];
int fun(int a) {
	memset(dp,0,sizeof dp);
	dp[0][0]=1;
	for(int i=0; i<=n; ++i) {
		for(int j=max(0ll,i-a); j<=min(m,i+k-a); ++j) {
			dp[i+1][j]+=dp[i][j],dp[i][j+1]+=dp[i][j];
			dp[i+1][j]%=p,dp[i][j+1]%=p;
		}
	}
	return dp[n][m];
}
signed main() {
	std::ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k>>p;
	facn=facm=1;
	for(int i=1; i<=n; ++i)facn=facn*i%p;
	for(int i=1; i<=m; ++i) facm=facm*i%p;
	for(int a=0; a<=k; ++a) if(m>=n-a&&m<=n+k-a)ans=(ans+fun(a))%p;
	--k;
	for(int a=0; a<=k; ++a) if(m>=n-a&&m<=n+k-a)ans=(ans-fun(a)+p)%p;
	cout<<ans*facn%p*facm%p<<"\n";
	return 0;
}

洛谷P2592 [ZJOI2008] 生日聚会

改编，且数据有加强。

小蓝提。

考虑 $DP$ ，我们直接考虑正解该怎么搞，显然我们只要考虑一个后缀的差就好了。 然后我们设 $f_{i,j,l,len}$ 表示后缀的范围是 $[l,l+len-1]$ ，$i$ 头公牛， $j$ 头母牛的方案，转移显然。

这样做时间复杂度是 $O(nmk^2)$，然后你注意到当 $i$ 一定时 $j$ 的范围其实非常有限，然后就可以做到 $O(nk^3)$

然后我们就发现其实我们已经几乎过了，因为我是最后发现 $NH$ 加强数据了，于是我加了家卡常，具体内容见代码。

CODE

#include<bits/stdc++.h>
using namespace std;
signed mod;
signed f[2][102][52][102];
inline signed Mod(signed tmp){//取模优化 
	if(tmp>=mod)tmp-=mod;
	return tmp;
}
signed main(){
	signed n,m,k;
	scanf("%d%d%d%d",&n,&m,&k,&mod);
	if(abs(m-n)>k){
		printf("0");
		return 0;
	}//特判 
	int eps=k;
	bool now=0;
	f[0][eps][eps][1]=1;
	for(int i=0; i<=n; i++){
		memset(f[now^1],0,sizeof f[now^1]);
		for(int j=i-k,delt=-k; j<=i+k; j++,delt++){
			if(j<0||j>m)continue;
			for(int l=0; l<=k; l++){
				for(int len=1; l+len-1<=2*k; len++){
					if((!f[now][delt+eps][l][len])){//有很多项是空的跳过 
						continue;
					}
					int r=l+len-1;
					int L=min(eps,l+1),R=max(eps,r+1);
					if(delt+eps-1>=0&&R<=2*k)
						f[now^1][delt+eps-1][L][R-L+1]=Mod(f[now^1][delt+eps-1][L][R-L+1]+f[now][delt+eps][l][len]);
					L=min(eps,l-1),R=max(eps,r-1);
					if(delt+eps+1<=2*k&&L>=0)
						f[now][delt+1+eps][L][R-L+1]=Mod(f[now][delt+1+eps][L][R-L+1]+f[now][delt+eps][l][len]);
				}
			}
		}
		now^=1;
	}now^=1;
	long long res=0;
	for(int i=0; i<=2*k; i++){
		for(int len=1; i+len-1<=2*k; len++){
			res=(res+f[now][m-n+eps][i][len])%mod;
		}
	}
	for(int i=1; i<=n; i++)res=res*i%mod;
	for(int i=1; i<=m; i++)res=res*i%mod;
	cout<<res<<endl;
	bool T2;
	return 0;
}/*
996 987 50 998244353

*/