In this HackerRank Tastes Like Winning problem solution Stephanie just learned about a game called Nim in which there are two players and N piles of stones. During each turn, a player must choose any non-empty pile and take as many stones as they want. The first player who cannot complete their turn (i.e., because all piles are empty) loses.
Stephanie knows that, for each start position in this game, it's possible to know which player will win (i.e., the first or second player) if both players play optimally. Now she wants to know the number of different games that exist that satisfy all of the following conditions:
- The game starts with N non-empty piles and each pile contains less than 2 to power m stones.
- All the piles contain pairwise different numbers of stones.
- The first player wins if that player moves optimally.
Help Stephanie by finding and printing the number of such games satisfying all the above criteria, modulo 10 to power 9 plus 7.
Problem solution in Python.
# Hacker Rank Challenge 15 hard
import sys
n,m = list(map(int,sys.stdin.readline().split()))
p = 1000000007
def pow_mod(x, y, z):
number = 1
while y:
if y & 1:
number = number * x % z
y >>= 1
x = x * x % z
return number
S = pow_mod(2,m,p)-1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2,m,p)
x = z1-1
for i in range(2,n+1):
x -= 1
A3 = (i * (S-W) * x)%p
S = (S*x)%p
W = (S-A1)
A1 = (W - A3)
#A2 = (S-W)
print(W%p)
#end of the programProblem solution in Java.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class TastesLikeWinning {
private static final long mod = 1000000007;
private static long m;
private static long pow;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
m = in.nextLong();
pow = pow(2, m);
long[] solves = new long[n+1];
long[] semiSolves = new long[n+1];
long[] products = new long[n+1];
semiSolves[0] = 1;
semiSolves[1] = 0;
products[0] = 1;
products[1] = (pow - 1 + mod) % mod;
solves[0] = 0;
solves[1] = products[1];
for (int i = 2; i <= n; i++){
products[i] = (((pow - i + mod) % mod) * products[i-1]) % mod;
semiSolves[i] =
(solves[i-1] - ((i-1) * ((semiSolves[i-2] * ((pow - 1 - (i-2) + mod) % mod)) % mod)) % mod + mod) % mod;
solves[i] = (products[i] - semiSolves[i] + mod) % mod;
}
System.out.println(solves[n]);
}
private static long pow(long b, long p){
if (p == 0) return 1;
if (p % 2 == 1) return 2 * pow(b, p - 1) % mod;
long q = pow(b, p / 2);
return q * q % mod;
}
}Problem solution in C++.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = (int)1e7 + 1, mod = (int)1e9 + 7;
int n, m, pw, ways, f[maxn];
int main() {
scanf("%d%d", &n, &m);
++pw;
for(int i = 0; i < m; ++i)
(pw <<= 1) >= mod && (pw -= mod);
f[0] = ways = 1;
for(int i = 1; i <= n; ++i) {
f[i] = (ways - f[i - 1] - (i - 1LL) * (pw - i + 1) % mod * f[i - 2]) % mod;
ways = (LL)ways * (pw - i) % mod;
}
f[n] < 0 && (f[n] += mod);
(ways -= f[n]) < 0 && (ways += mod);
printf("%d\n", ways);
return 0;
}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 MOD 1000000007
char* readline();
char** split_string(char*);
/*
* Complete the tastesLikeWinning function below.
*/
int tastesLikeWinning(int n, int m) {
long *power2 = malloc((m + 1)*sizeof(long));
assert(power2 != NULL);
power2[0] = 1;
for(int i = 1; i <= m; i++){
power2[i] = (power2[i - 1]*2)%MOD;
}
long *tLL = malloc((n + 1)*sizeof(long));
assert(tLL != NULL);
long *tLW = malloc((n + 1)*sizeof(long));
assert(tLW != NULL);
tLL[0] = 1;
tLL[1] = 0;
tLW[0] = 0;
tLW[1] = power2[m] - 1;
for(int i = 2; i <= n; i++){
long temp = (power2[m] + MOD - i)%MOD;
long temp2 = ((temp + 1)*(i - 1))%MOD;
tLL[i] = (tLW[i - 1] + tLL[i - 2]*(MOD - temp2))%MOD;
tLW[i] = (((tLL[i - 1]*temp)%MOD) + ((tLW[i - 1]*(temp + MOD - 1))%MOD) + (tLL[i - 2]*temp2)%MOD)%MOD;
}
return tLW[n];
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
char** nm = split_string(readline());
char* n_endptr;
char* n_str = nm[0];
int n = strtol(n_str, &n_endptr, 10);
if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }
char* m_endptr;
char* m_str = nm[1];
int m = strtol(m_str, &m_endptr, 10);
if (m_endptr == m_str || *m_endptr != '\0') { exit(EXIT_FAILURE); }
int result = tastesLikeWinning(n, m);
fprintf(fptr, "%d\n", result);
fclose(fptr);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
if(data[data_length] != '\0'){
data_length++;
data = realloc(data, data_length);
data[data_length - 1] = '\0';
}
data = realloc(data, data_length);
return data;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
0 Comments