In this HackerRank King and Four Sons problem solution The King tasks you with finding the number of ways of selecting K detachments of battalions to capture K countries using the criterion that is given by the problem.
Problem solution in Python.
import math
MOD = int(1e9 + 7)
ans=[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
def S_(n, k):
def cnk(n, k):
return int(math.factorial(n) // (math.factorial(k) * math.factorial(n - k)))
return sum(cnk(n, i) for i in range(k, n + 1, 4)) % MOD
def S(n, k = 0):
if n < 5:
return sum(ans[n][k::4])
r = pow(2, n - 2, MOD) - pow(2, n // 2, MOD)
if n & 1:
r = (r + pow(2, (n - 3) // 2, MOD) * sum(ans[3][(k - (n - 3)// 2) % 4::4])) % MOD
else:
r = (r + pow(2, (n - 3) // 2, MOD) * sum(ans[4][(k - (n - 3)// 2) % 4::4])) % MOD
return int(r)
n, k = map(int, input().split())
a = list(map(int, input().split()))
det = [S(i) for i in a]
mem = [[float("+inf")] * (i + 1) for i in range(n + 1)]
mem[0][0] = 1
for i in range(1, n + 1):
mem[i][1] = sum(det[:i]) % MOD
mem[i][i] = (mem[i - 1][i - 1] * det[i - 1]) % MOD
for i in range(3, n + 1):
for j in range(2, min(i, k + 1)):
mem[i][j] = (mem[i - 1][j] + mem[i - 1][j - 1] * det[i - 1]) % MOD
print(mem[n][k])
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
private static InputReader in;
private static PrintWriter out;
public static long mod = 1000000007;
public static long INV4 = pow(new Complex(4,0), mod-2).a;
static class Complex {
public long a,b;
public Complex(long a, long b) {
this.a = a;
this.b = b;
if (a < 0) a += mod;
}
public Complex multiply(Complex other) {
return new Complex((a * other.a + mod - (b * other.b % mod)) % mod, (a * other.b + b * other.a) % mod);
}
}
public static Complex pow(Complex a, long e) {
Complex r = new Complex(1,0);
while(e>0) {
if ((e&1)==1) r = r.multiply(a);
a = a.multiply(a);
e >>= 1;
}
return r;
}
public static long nways(long x) {
Complex s1 = pow(new Complex(1, 1), x);
Complex s2 = pow(new Complex(1, mod - 1), x);
Complex s3 = pow(new Complex(2, 0), x);
long res = (s3.a + s1.a + s2.a) % mod;
return res * INV4 % mod;
}
public static void main(String[] args) throws IOException {
in = new InputReader(System.in);
out = new PrintWriter(System.out, true);
int n = in.nextInt();
int k = in.nextInt();
long[] dp = new long[k+1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
long m = nways(in.nextInt());
long[] next = new long[k+1];
System.arraycopy(dp, 0, next, 0, k+1);
for (int j = 0; j < k; j++) {
next[j+1] = (next[j+1] + dp[j] * m) % mod;
}
dp = next;
}
out.println(dp[k]);
out.close();
System.exit(0);
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
Problem solution in C++.
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const int nax = 1e6 + 5;
const int mod = 1e9 + 7;
pii mul(pii a, pii b) {
ll c = (ll) a.st * b.st - (ll) a.nd * b.nd;
ll d = (ll) a.st * b.nd + (ll) a.nd * b.st;
c %= mod;
d %= mod;
if(c < 0) c += mod;
if(d < 0) d += mod;
return mp((int) c, (int) d);
}
pii pw(pii a, int k) {
pii r = mp(1, 0);
while(k) {
if(k % 2) r = mul(r, a);
a = mul(a, a);
k /= 2;
}
return r;
}
int pw(int a, int k) {
int r = 1;
while(k) {
if(k % 2) r = (ll) r * a % mod;
a = (ll) a * a % mod;
k /= 2;
}
return r;
}
int f(int n) {
int r = pw(mp(1,mod-1), n).st + pw(mp(1,1), n).st;
r %= mod;
r += pw(2, n);
r %= mod;
r = (ll) r * pw(4, mod - 2) % mod;
return r;
}
int dp[105];
int main() {
int n, k;
scanf("%d%d", &n, &k);
dp[0] = 1;
REP(_, n) {
int a;
scanf("%d", &a);
a = f(a);
FORD(j, k, 1)
dp[j] = (dp[j] + (ll) dp[j-1] * a) % mod;
}
printf("%dn", dp[k]);
return 0;
}
Problem solution in C.
#include<stdio.h>
#include<stdlib.h>
#define CLOCK 1000000007
#define MODINV4 250000002
long int c[10000], M[10001][101];
long int fast_exp(long int x, int n, int clock)
{
if( n == 0 )
{
return 1;
}
long int y = 1;
while( n > 1 )
{
if( n % 2 == 0 )
{
x = x * x % clock;
n = n / 2;
}
else
{
y = x * y % clock;
x = x * x % clock;
n = ( n - 1 ) / 2;
}
}
return x * y % clock;
}
void compute_combinations(int n, int *army)
{
int vals[4] = { 2, 2, 0, -4 };
for( int i = 0 ; i < n ; i++ )
{
int div = army[i] / 4;
int rem = army[i] % 4;
if( div % 2 == 0 )
{
c[i] = fast_exp(2, army[i], CLOCK) + fast_exp(4, div, CLOCK) * ( vals[rem] + CLOCK );
}
else
{
c[i] = fast_exp(2, army[i], CLOCK) - fast_exp(4, div, CLOCK) * ( vals[rem] - CLOCK );
}
c[i] %= CLOCK;
c[i] = c[i] * MODINV4 % CLOCK;
}
}
int king(int n, int k, int* army)
{
compute_combinations(n, army);
for( int i = 0 ; i <= n ; i++ )
{
M[i][0] = 1;
}
for( int i = 1 ; i <= n ; i++ )
{
for( int j = 1 ; j <= k ; j++ )
{
M[i][j] = c[i - 1] * M[i - 1][j - 1] + M[i - 1][j];
M[i][j] %= CLOCK;
}
}
return M[n][k];
}
int main()
{
FILE *fptr = fopen(getenv("OUTPUT_PATH"), "w");
int n, k;
scanf("%d %d", &n, &k);
int *army = malloc(n * sizeof(int));
for( int i = 0 ; i < n ; i++ )
{
scanf("%d", &army[i]);
}
fprintf(fptr, "%dn", king(n, k, army));
fclose(fptr);
return 0;
}