In this HackerRank Dortmund Dilemma problem solution, we have given the length N of Letter and number of K different letters from thw 26 letters of the English alphabet. and we need to find the number of easy names we can choose.
Problem solution in Python.
def func(): MOD = (10 ** 9) + 9 Max = (10 ** 5) + 1 nCr = [[1]] for n in range(1, 27): m = [1] for k in range(1, n): m.append(nCr[-1][k] + nCr[-1][k - 1]) m.append(1) nCr.append(m) DP = [[]] for k in range(1, 27): FDP = [1] for i in range(1, Max): temp = FDP[-1] * k if i % 2 == 0: temp = temp - FDP[i // 2] FDP.append(temp % MOD) DP.append(FDP) for t in range(int(input())): N, K = map(int, input().split()) G = [0] for i in range(1, K + 1): G.append(pow(i, N, MOD) - DP[i][N] - sum(G[j] * nCr[i][j] for j in range(1, i)) % MOD) print(G[-1] * nCr[26][K] % MOD) func()
Problem solution in Java.
import java.util.Scanner;
public class DortmundDilemma {
public static final int MAX_N = 100000;
public static final int MAX_K = 26;
public static final long MOD = 1000000009;
static long[][] C;
static long[][] F;
static long[][] G;
static long[][] P;
public static void main(String[] args) {
C = new long[MAX_K+1][MAX_K+1];
for (int i = 0; i <= MAX_K; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) {
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
}
}
F = new long[MAX_N+1][MAX_K+1];
G = new long[MAX_N+1][MAX_K+1];
P = new long[MAX_N+1][MAX_K+1];
for (int k = 1; k <= MAX_K; k++) {
F[1][k] = k;
long kn = k;
for (int n = 2; n <= MAX_N; n++) {
kn = kn * k % MOD;
if (n % 2 == 1) {
F[n][k] = F[n-1][k] * k % MOD;
} else {
F[n][k] = (F[n-1][k] * k % MOD - F[n/2][k] + MOD) % MOD;
}
G[n][k] = (kn - F[n][k] + MOD) % MOD;
P[n][k] = G[n][k];
for (int j = 1; j < k; j++) {
P[n][k] = (P[n][k] - P[n][j] * C[k][j] % MOD + MOD) % MOD;
}
}
}
Scanner scanner = new Scanner(System.in);
for (int t = scanner.nextInt(); t > 0; t--) {
int N = scanner.nextInt(), K = scanner.nextInt();
System.out.println(P[N][K] * C[26][K] % MOD);
}
scanner.close();
}
}Problem solution in C++.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <assert.h>
#define fo(i,a,b) dfo(int,i,a,b)
#define fr(i,n) dfr(int,i,n)
#define fe(i,a,b) dfe(int,i,a,b)
#define fq(i,n) dfq(int,i,n)
#define nfo(i,a,b) dfo(,i,a,b)
#define nfr(i,n) dfr(,i,n)
#define nfe(i,a,b) dfe(,i,a,b)
#define nfq(i,n) dfq(,i,n)
#define dfo(d,i,a,b) for (d i = (a); i < (b); i++)
#define dfr(d,i,n) dfo(d,i,0,n)
#define dfe(d,i,a,b) for (d i = (a); i <= (b); i++)
#define dfq(d,i,n) dfe(d,i,1,n)
#define ffo(i,a,b) dffo(int,i,a,b)
#define ffr(i,n) dffr(int,i,n)
#define ffe(i,a,b) dffe(int,i,a,b)
#define ffq(i,n) dffq(int,i,n)
#define nffo(i,a,b) dffo(,i,a,b)
#define nffr(i,n) dffr(,i,n)
#define nffe(i,a,b) dffe(,i,a,b)
#define nffq(i,n) dffq(,i,n)
#define dffo(d,i,a,b) for (d i = (b)-1; i >= (a); i--)
#define dffr(d,i,n) dffo(d,i,0,n)
#define dffe(d,i,a,b) for (d i = (b); i >= (a); i--)
#define dffq(d,i,n) dffe(d,i,1,n)
#define ll long long
#define alok(n,t) ((t*)malloc((n)*sizeof(t)))
#define pf printf
#define sf scanf
#define pln pf("\n")
#define mod 1000000009
#define bet(a,b,c) ((a)<=(b)&&(b)<=(c))
#define K 26
#define N 111111
ll _i[K+1];
ll C[K+1][K+1];
ll _p[K+1][2*N+1];
ll _q[K+1][2*N+1];
ll _s[K+1][N+1];
ll _g[K+1][N+1];
ll _t[K+1][N+1];
int main() {
fe(k,0,K) {
if (k == 0) {
_i[k] = 0;
} else if (k == 1) {
_i[k] = 1;
} else {
_i[k] = (mod - mod/k) * _i[mod % k] % mod;
}
}
fe(n,0,K) fe(r,0,K) {
if (r < 0 or r > n) {
C[n][r] = 0;
} else if (r == 0 or r == n) {
C[n][r] = 1;
} else {
C[n][r] = (C[n-1][r-1] + C[n-1][r]) % mod;
}
}
fe(k,0,K) fe(n,0,2*N) {
if (n == 0) {
_p[k][n] = 1;
} else {
_p[k][n] = _p[k][n-1] * k % mod;
}
if (n == 0) {
_q[k][n] = 1;
} else {
_q[k][n] = _q[k][n-1] * _i[k] % mod;
}
}
fe(k,0,K) fe(n,0,N) {
if (k == 1) {
if (n <= 1) {
_g[k][n] = 0;
} else {
_g[k][n] = _q[k][2*n];
}
} else {
ll s = (_p[k][n/2]-1) * _i[k-1] % mod * _p[k][(n+1)/2];
ll t = _s[k][n/2] * _p[k][n];
_g[k][n] = (s - t) % mod * _q[k][2*n] % mod;
}
if (n == 0) {
_s[k][n] = 0;
} else {
_s[k][n] = (_s[k][n-1] + _g[k][n]) % mod;
}
if (k == 0) {
_t[k][n] = 0;
} else {
ll ct = _p[k][2*n] * _g[k][n] % mod;
fr(kk,k) {
ct -= C[k][kk] * _t[kk][n];
ct %= mod;
}
_t[k][n] = ct;
}
}
int z;
sf("%d", &z);
assert(bet(1,z,100000));
while (z--) {
int n, k;
sf("%d%d", &n, &k);
assert(bet(1,n,100000));
assert(bet(1,k,26));
ll ans = _t[k][n] * C[26][k] % mod;
if (ans < 0) ans += mod;
pf("%lld\n", ans);
}
}Problem solution in C.
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FOR(i, a, b) for(__typeof(a) i=(a); i<(b); i++)
#define MEM(x,val) memset((x),(val),sizeof(x));
#define MOD 1000000009
#define N 100000
#define K 26
typedef long long ll;
char* readline();
char** split_string(char*);
void print_matrix(int n, int m, ll arr[n][m]) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
printf("%lld ", arr[i][j]);
}
putchar('\n');
}
}
ll cdp[K+1][K+1];
ll comb(ll n, ll k){
if(k > n) return 0;
if(n == k) return 1;
if(k == 0) return 1;
if(k == 1) return n % MOD;
if(cdp[n][k]==-1) cdp[n][k] = ( comb(n-1,k-1) + comb(n-1,k) ) % MOD;
return cdp[n][k];
}
ll dp[N+1][K+1];
void init() {
MEM(cdp, -1);
FOR(k, 1, K+1) {
FOR(n, 1, N+1) {
if(n==1) dp[n][k] = k;
else {
dp[n][k] = (n % 2 ? (dp[n-1][k]*k)%MOD:
(dp[n-1][k]*k)%MOD - dp[n/2][k]
) % MOD;
if(dp[n][k] < 0) dp[n][k] += MOD;
}
}
}
FOR(k, 1, K+1) {
ll kN = 1;
FOR(n, 1, N+1) {
kN = kN*k % MOD;
dp[n][k] = kN - dp[n][k];
if(dp[n][k] < 0) dp[n][k] += MOD;
FOR(j, 1, k) {
dp[n][k] -= (dp[n][j]*comb(k,j)) % MOD;
if(dp[n][k] < 0) dp[n][k] += MOD;
}
}
}
}
int main()
{
init();
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
int t;
scanf("%d", &t);
while (t--) {
int n, k;
scanf("%d %d", &n, &k);
assert(1 <= n && n <= 100000);
assert(1 <= k && k <= 26);
fprintf(fptr, "%lld\n", (dp[n][k]*comb(26,k))%MOD);
}
fclose(fptr);
}
0 Comments