C++(g++ 7.5.0) 解法, 执行用时: 105ms, 内存消耗: 57452K, 提交时间: 2023-06-24 22:07:19

#include<bits/stdc++.h>
using namespace std;
const int N=3e5;
const int M=1e6;
const int mod=12345678;
const int INF=0x3f3f3f3f;
int n,m,k;
int dp[155][155][25][25];
int main(){
    ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	dp[0][0][0][0]=1;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int k1=0;k1<=k;k1++)
				for(int k2=0;k2<=k;k2++){
					int tmp=dp[i][j][k1][k2];
					dp[i+1][j][k1+1][max(0,k2-1)]=(dp[i+1][j][k1+1][max(0,k2-1)]+tmp)%mod;
					dp[i][j+1][max(0,k1-1)][k2+1]=(dp[i][j+1][max(0,k1-1)][k2+1]+tmp)%mod;
				}
	int ans=0;
	for(int i=0;i<=k;i++)
		for(int j=0;j<=k;j++)
			ans=(ans+dp[n][m][i][j])%mod;
	cout<<ans;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 36ms, 内存消耗: 10084K, 提交时间: 2020-04-01 17:14:32

#include<cstdio>
#include<algorithm>
using namespace std;
int f[151][151][21][21],n,m,K,ans;
int main()
{
	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]) continue;
		if(i<n&&k<K) 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])%12345678;
		if(j<m&&l<K) 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])%12345678; 
	}
	for(int i=0;i<=K;i++)
	for(int j=0;j<=K;j++)
	ans=(ans+f[n][m][i][j])%12345678;
	printf("%d",ans);
}