Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "Balls and Boxes 4"
https://onlinejudge.u-aizu.ac.jp/problems/DPL_5_D
・ボールと箱4
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #DPL_5_D : Balls and Boxes 4
/* Aizu Online Judge in C++ #DPL_5_D : Balls and Boxes 4 https://onlinejudge.u-aizu.ac.jp/problems/DPL_5_D 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll m=1e9+7; ll dp[2010][1010]; ll DFS(ll a,ll b){ if(a==b){ return 1; } if(dp[a][b]){ return dp[a][b]; } ll num=0; if(a){ num+=DFS(a-1,b); } if(a && b){ num+=DFS(a-1,b-1); } num%=m; return dp[a][b]=num; } int main(void){ ll n,k; cin>>n>>k; dp[0][0]=1; cout<<DFS(n+k-1,k-1)<<endl; return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/