In this HackerRank Unique Divide And Conquer problem solution we have Given the number of vertices N, count the number of tree T’s such that the Divide-and-Conquer approach works determinately on them. As this number can be quite large, your answer must be modulo M.
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
FastScanner in;
PrintWriter out;
void solve() {
int n = in.nextInt();
int p = in.nextInt();
int[][] c = new int[n + 1][n + 1];
c[0][0] = 1;
for (int i = 1; i <= n; i++) {
c[i][0] = 1;
for (int j = 1; j <= n; j++) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
if (c[i][j] >= p) {
c[i][j] -= p;
}
}
}
long[] dpSum = new long[n + 1];
long[] ans = new long[n + 1];
long[] dpBad = new long[n + 1];
dpSum[0] = 1;
for (int sz = 1; sz <= n; sz++) {
for (int big = (1 + sz) / 2; big < sz; big++) {
dpBad[sz] += dpSum[sz - 1 - big] * ans[big] % p * big % p
* c[sz - 1][big] % p;
}
dpBad[sz] %= p;
ans[sz] = (dpSum[sz - 1] - dpBad[sz] + p) * sz % p;
for (int size1 = 1; size1 <= sz; size1++) {
dpSum[sz] += ans[size1] * size1 % p * c[sz - 1][size1 - 1] % p
* dpSum[sz - size1] % p;
}
dpSum[sz] %= p;
}
out.println(ans[n]);
}
void run() {
try {
in = new FastScanner(new File("object.in"));
out = new PrintWriter(new File("object.out"));
solve();
out.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
void runIO() {
in = new FastScanner(System.in);
out = new PrintWriter(System.out);
solve();
out.close();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
public FastScanner(File f) {
try {
br = new BufferedReader(new FileReader(f));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public FastScanner(InputStream f) {
br = new BufferedReader(new InputStreamReader(f));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
String s = null;
try {
s = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
if (s == null)
return null;
st = new StringTokenizer(s);
}
return st.nextToken();
}
boolean hasMoreTokens() {
while (st == null || !st.hasMoreTokens()) {
String s = null;
try {
s = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
if (s == null)
return false;
st = new StringTokenizer(s);
}
return true;
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
public static void main(String[] args) {
new Solution().runIO();
}
}
Problem solution in C++.
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <deque>
#include <string>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#define pb push_back
#define pbk pop_back
#define mp make_pair
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define len(a) ((int) (a).size())
#ifdef CUTEBMAING
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif
using namespace std;
typedef long long int64;
typedef long double ld;
typedef unsigned long long lint;
const int inf = (1 << 30) - 1;
const int64 linf = (1ll << 62) - 1;
const int N = 1e4 + 100;
int M;
inline int power(int a, int b) {
int res = 1;
while (b) {
if (b & 1) {
res = (1ll * res * a) % M;
}
a = (1ll * a * a) % M;
b >>= 1;
}
return res;
}
inline int inv(int x) {
return power(x, M - 2);
}
int n;
int fact[N], ifact[N];
void precalc() {
fact[0] = ifact[0] = 1;
for (int i = 1; i <= n; i++) {
fact[i] = (1ll * fact[i - 1] * i) % M;
ifact[i] = (1ll * ifact[i - 1] * inv(i)) % M;
}
}
int f[N], dp[N];
int main() {
cin >> n >> M;
precalc();
f[1] = 1;
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = dp[i - 1];
for (int j = (i + 1) / 2; j <= i - 1; j++) {
int cur1 = (1ll * f[j] * fact[i - 1]) % M;
int cur2 = (1ll * cur1 * ifact[j]) % M;
int cur3 = (1ll * cur2 * ifact[i - 1 - j]) % M;
int cur4 = (1ll * cur3 * j) % M;
f[i] -= (1ll * cur4 * dp[i - j - 1]) % M;
if (f[i] < 0) {
f[i] += M;
}
}
f[i] = (1ll * f[i] * i) % M;
for (int j = 1; j <= i; j++) {
int cur1 = (1ll * f[j] * fact[i - 1]) % M;
int cur2 = (1ll * cur1 * ifact[j - 1]) % M;
int cur3 = (1ll * cur2 * ifact[i - j]) % M;
int cur4 = (1ll * cur3 * j) % M;
dp[i] = (dp[i] + 1ll * cur4 * dp[i - j]) % M;
}
}
printf("%dn", f[n]);
return 0;
}
Problem solution in C.
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 3001
typedef long long ll;
int f[N],g[N],c[N][N],n,p;
int main()
{
scanf("%d%d",&n,&p);
g[0]=1;
f[1]=g[1]=1;
f[2]=0; g[2]=1;
fo(i,0,n) c[i][0]=1;
fo(i,1,n)
fo(j,1,i) c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
f[0]=1;
fo(i,3,n)
{
if (i&1)
{
f[i]=g[i-1];
fo(j,i/2+1,i-1) f[i]=(f[i]-(ll)g[i-1-j]*f[j]%p*j%p*c[i-1][j])%p;
int half=i/2;
f[i]=(ll)f[i]*i%p;
} else
{
f[i]=g[i-1];
fo(j,i/2,i-1) f[i]=(f[i]-(ll)g[i-1-j]*f[j]%p*j%p*c[i-1][j])%p;
f[i]=(ll)f[i]*i%p;
}
fo(j,1,i)
g[i]=(g[i]+(ll)g[i-j]*c[i-1][j-1]%p*f[j]%p*j%p)%p;
}
printf("%dn",(f[n]+p)%p);
}
