HackerRank-Project-Euler-Solutions/Problem_#78_Coin_partitions.cpp at main · nalin88/HackerRank-Project-Euler-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<double, double> dd;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

const int N = 1e5;
const int M = 1e9 + 7;
int main(){
	vii pentagonal; // Wikipedia: partitions
	int m = -400;
	while(m < 400){ // x^2 < N
		m++;
		if(m == 0) continue;
		pentagonal.push_back(ii(abs((m*(3*m-1))/2), (abs(m)%2)*2 -1));
	}
	sort(pentagonal.begin(), pentagonal.end());

	vector<ll> v(N, 0);
	v[0] = 1;
	for(int i=1;i<N;i++){
		for(int j=0; pentagonal[j].first <= i; j++){
			v[i] += v[i-pentagonal[j].first]*pentagonal[j].second;
			while(v[i] < 0) v[i] += M;
			v[i] %= M;
		}
	}

	int t;cin >> t;
	while(t--){
		int n; cin >> n;
		cout << v[n] <<endl;
	}


}