Unique Divide And Conquer
Problem Statement :
Divide-and-Conquer on a tree is a powerful approach to solving tree problems. Imagine a tree, t, with n vertices. Let's remove some vertex v from tree t, splitting t into zero or more connected components, t1,t2,...,tk, with vertices n1,n2,...,nk. We can prove that there is a vertex, , such that the size of each formed components is at most [n/2]. The Divide-and-Conquer approach can be described as follows: Initially, there is a tree, t, with n vertices. Find vertex v such that, if v is removed from the tree, the size of each formed component after removing v is at most [n/2]. Remove v from tree t. Perform this approach recursively for each of the connected components. We can prove that if we find such a vertex v in linear time (e.g., using DFS), the entire approach works in O(n.logn). Of course, sometimes there are several such vertices v that we can choose on some step, we can take and remove any of them. However, right now we are interested in trees such that at each step there is a unique vertex v that we can choose. Given 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. Input Format A single line of two space-separated positive integers describing the respective values of n (the number of vertices in tree t) and m (the modulo value). Constraints 1 <= n <= 3000 n < m <= 10^9 m is a prime number.
Solution :
Solution in C :
In C++ :
#include <bits/stdc++.h>
using namespace std;
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod;
vector<ll> fact, ifact;
vector<int> mem;
vector<vector<int>> mem2;
ll solve2(int left, int max);
ll rsolve(int n) {
if (n <= 5) return n != 2;
return solve2(n-1, (n-1)/2);
}
ll solve(int n) {
assert(n > 0);
int& out = mem[n];
if (out != -1) return out;
return out = (int)(rsolve(n) * n % mod);
}
ll solve2(int left, int max) {
if (left == 0) return 1;
if (!max) return 0;
int& out = mem2[left][max];
if (out != -1) return out;
ll res = solve2(left, max-1);
if (max > left) return out = (int)res;
int lim = left / max;
ll one = solve(max) * max % mod * ifact[max] % mod;
ll mult = one * fact[left] % mod;
for (int i = 1;; i++) {
ll bin = ifact[i] * ifact[left - i * max] % mod;
res += solve2(left - i * max, max-1) * mult % mod * bin;
if (i == lim) break;
if (i % 4 == 0) res %= mod;
mult = mult * one % mod;
}
res %= mod;
return out = (int)res;
}
int main() {
cin.sync_with_stdio(false);
cin.exceptions(cin.failbit);
int N;
cin >> N >> mod;
mem.assign(N+1, -1);
mem2.assign(N+1, vector<int>(N+1, -1));
int LIM = N+1;
ll* inv = new ll[LIM] - 1; inv[1] = 1;
rep(i,2,LIM) inv[i] = mod - (mod / i) * inv[mod % i] % mod;
fact.resize(N+1);
ifact.resize(N+1);
fact[0] = ifact[0] = 1;
rep(i,1,N+1) {
fact[i] = fact[i-1] * i % mod;
ifact[i] = ifact[i-1] * inv[i] % mod;
}
cout << solve(N) << endl;
exit(0);
}
In Java :
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
DivideAndConquer solver = new DivideAndConquer();
solver.solve(1, in, out);
out.close();
}
static class DivideAndConquer {
public void solve(int testNumber, InputReader in, PrintWriter out) {
int n = in.nextInt();
int mod = in.nextInt();
int[] trees = new int[n + 1];
int[][] choose = new int[n + 1][n + 1];
for (int i = 0; i < choose.length; i++) {
choose[i][0] = choose[i][i] = 1;
for (int j = 1; j < i; j++) {
choose[i][j] = (choose[i - 1][j - 1] + choose[i - 1][j]) % mod;
}
}
trees[0] = 1;
trees[1] = 1;
int[] ways = new int[n];
ways[0] = 1;
int maxTreeSize = 1;
for (int size = 1; size < n; size++) {
if (size > (n - 1) / 2 && size != n - 1) {
continue;
}
for (; maxTreeSize <= size / 2; maxTreeSize++) {
int[] thing = new int[n / maxTreeSize + 1];
thing[0] = 1;
for (int cnt = 1; cnt < thing.length; cnt++) {
long cur = (long) thing[cnt - 1] * trees[maxTreeSize] % mod;
cur = cur * choose[cnt * maxTreeSize - 1][maxTreeSize - 1] % mod;
cur = cur * maxTreeSize % mod;
thing[cnt] = (int) cur;
}
for (int toSize = n - 1; toSize >= 0; --toSize) {
for (int cnt = 1; cnt * maxTreeSize <= toSize; cnt++) {
int wasSize = toSize - maxTreeSize * cnt;
long cur = (long) ways[wasSize] * thing[cnt] % mod;
cur = cur * choose[toSize][wasSize];
ways[toSize] = (int) ((ways[toSize] + cur) % mod);
}
}
}
trees[size + 1] = (int) ((long) ways[size] * (size + 1) % mod);
}
out.println(trees[n]);
}
}
static class InputReader {
public BufferedReader br;
StringTokenizer st;
public InputReader(InputStream stream) {
br = new BufferedReader(new InputStreamReader(stream));
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
String line = null;
try {
line = br.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
if (line == null) {
return null;
}
st = new StringTokenizer(line);
}
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(nextToken());
}
}
}
In C :
#include <stdio.h>
#include <stdlib.h>
long long modInverse(long long a,long long mod);
long long dp3[3001][3001],dp4[3001],fac[3001],ifac[3001],iifac[3001][3001];
int main(){
int n,m,i,j,k,l;
long long t2;
scanf("%d%d",&n,&m);
for(i=fac[0]=ifac[0]=1;i<=n;i++){
fac[i]=fac[i-1]*i%m;
ifac[i]=modInverse(fac[i],m);
}
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
iifac[i][j]=ifac[i]*ifac[j]%m;
for(i=0;i<=n;i++)
dp3[i][0]=1;
for(i=1,dp4[1]=1;i<=(n-1)/2;i++){
for(j=1;j<n;j++)
for(k=1,t2=fac[j]*dp4[i]%m,dp3[i][j]=dp3[i-1][j];k*i<=j;k++,t2=t2*dp4[i]%m){
l=j-k*i;
dp3[i][j]=(dp3[i][j]+t2*iifac[l][k]%m*dp3[i-1][l])%m;
}
dp4[i+1]=dp3[i/2][i]*(i+1)%m*(i+1)%m*ifac[i+1]%m;
}
printf("%lld",dp3[(n-1)/2][n-1]*n%m);
return 0;
}
long long modInverse(long long a,long long mod){
long long b0 = mod, t, q;
long long x0 = 0, x1 = 1;
while (a > 1) {
q = a / mod;
t = mod; mod = a % mod; a = t;
t = x0; x0 = x1 - q * x0; x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}
View More Similar Problems
Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →Tree : Top View
Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.
View Solution →Tree: Level Order Traversal
Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F
View Solution →Binary Search Tree : Insertion
You are given a pointer to the root of a binary search tree and values to be inserted into the tree. Insert the values into their appropriate position in the binary search tree and return the root of the updated binary tree. You just have to complete the function. Input Format You are given a function, Node * insert (Node * root ,int data) { } Constraints No. of nodes in the tree <
View Solution →Tree: Huffman Decoding
Huffman coding assigns variable length codewords to fixed length input characters based on their frequencies. More frequent characters are assigned shorter codewords and less frequent characters are assigned longer codewords. All edges along the path to a character contain a code digit. If they are on the left side of the tree, they will be a 0 (zero). If on the right, they'll be a 1 (one). Only t
View Solution →Binary Search Tree : Lowest Common Ancestor
You are given pointer to the root of the binary search tree and two values v1 and v2. You need to return the lowest common ancestor (LCA) of v1 and v2 in the binary search tree. In the diagram above, the lowest common ancestor of the nodes 4 and 6 is the node 3. Node 3 is the lowest node which has nodes and as descendants. Function Description Complete the function lca in the editor b
View Solution →
