/* * This solution is too slow, but helps you think about the correct solution. * * See the writeup for how this solution works. */ #include #include #include #include #include #include #include #include #include #include #include using namespace std; class Solution { public: int kInversePairs(int n, int k); vector < vector > Cache; }; long long BP = 1000000007; int Solution::kInversePairs(int n, int k) { long long i; long long sum; if (k == 0) return 1; if (n == 0) return 0; if (Cache.size() == 0) { Cache.resize(n+1); for (i = 0; i < Cache.size(); i++) Cache[i].resize(k+1, -1); } if (Cache[n][k] != -1) return Cache[n][k]; sum = 0; for (i = 0; i < n && i <= k; i++) { sum += kInversePairs(n-1, k-i); } Cache[n][k] = sum % BP; return Cache[n][k]; } int main() { int n, k; Solution s; cin >> n >> k; cout << s.kInversePairs(n, k) << endl; /* for (n = 0; n < s.Cache.size(); n++) { for (k = 0; k < s.Cache[n].size(); k++) { if (s.Cache[n][k] != -1) printf("%2d %2d %8d\n", n, k, s.Cache[n][k]); } } */ return 0; }