http://www.lydsy.com/JudgeOnline/problem.php?id=1037
好难想啊
//#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> using namespace std; /************************************************ Code By willinglive ************************************************/ ///////////////////////////////////////////////// const int mod=12345678; const int inf=300000; #define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++) #define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--) #define MS(arr,x) memset(arr,x,sizeof(arr)) #define LL long long #define INE(i,u,e) for(int i=head[u];~i;i=e[i].next) inline const LL getint() { LL r=0,k=1;char c=getchar(); for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1; for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0'; return k*r; } ///////////////////////////////////////////////// int n,m,k; int _dp[301][151][21][21]; #define dp(i,j,k,l) _dp[i][j][k][l] ///////////////////////////////////////////////// ///////////////////////////////////////////////// void input() { scanf("%d%d%d",&n,&m,&k); } void solve() { dp(0,0,0,0)=1; //dp[0][0][0][0]=1; rep(i,0,n+m-1) rep(j,0,n) { rep(p,0,k) rep(q,0,k) if(dp(i,j,p,q)) { if(p+1<=k&&j+1<=n) dp(i+1,j+1,p+1,max(q-1,0))+=dp(i,j,p,q),dp(i+1,j+1,p+1,max(q-1,0))%=mod; if(q+1<=k&&i+1-j<=m) dp(i+1,j,max(p-1,0),q+1)+=dp(i,j,p,q),dp(i+1,j,max(p-1,0),q+1)%=mod; } } int ans=0; rep(p,0,k) rep(q,0,k) ans+=dp(n+m,n,p,q),ans%=mod; printf("%d\n",ans); } ///////////////////////////////////////////////// int main() { #ifndef _TEST freopen("std.in","r",stdin); freopen("std.out","w",stdout); #endif input(); solve(); return 0; }