Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <unordered_map>
- using namespace std;
- typedef pair<int, int> pr;
- struct pair_hash {
- template <typename T1, typename T2>
- size_t operator () (const pair<T1, T2>& p) const {
- auto h1 = hash<T1>{}(p.first);
- auto h2 = hash<T2>{}(p.second);
- return h1 ^ h2;
- }
- };
- unordered_map<pr, int, pair_hash> us;
- int foo(int n, int k) {
- if (n == k && n > 0) return 1;
- else if (n > 0 && k == 1) return 1;
- else if (k > n) return 0;
- else {
- pr a = make_pair(n - 1, k - 1);
- pr b = make_pair(n - k, k);
- if (us.count(a) == 0) us[a] = foo(a.first, a.second);
- if (us.count(b) == 0) us[b] = foo(b.first, b.second);
- return us[a] + us[b];
- }
- }
- int main() {
- ifstream fin("input.txt");
- ofstream fout("output.txt");
- int n, k;
- fin >> n >> k;
- fout << foo(n, k);
- fin.close();
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment