Table of Contents
String Transmission – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include <cstdio>
#include <cstring>
const int mod = 1000000007;
#define MAXN 1005
int T, N, K;
char b[ MAXN ];
int c[ MAXN ][ MAXN ];
int cnt[ MAXN ][ 2 ];
int dp[ MAXN ];
int p[ MAXN ];
int main( void )
{
scanf( "%d", &T );
for( int i = 0; i < MAXN; ++i ) {
for( int j = 0; j < MAXN; ++j ) {
if( j > i ) continue;
if( i == 0 ) { c[i][j] = 1; continue; }
c[i][j] = c[i-1][j] + c[i-1][j-1];
if( c[i][j] > mod ) c[i][j] -= mod;
}
}
while( T-- ) {
scanf( "%d%d", &N, &K );
scanf( "%s", b );
for( int i = 1; i < N; ++i )
p[i] = 0;
int periodic = 0;
for( int i = 1; i < N; ++i ) {
if( N % i != 0 ) continue;
for( int j = 0; j < i; ++j )
cnt[j][0] = cnt[j][1] = 0;
for( int j = 0; j < N; ++j )
cnt[j%i][1-b[j]+'0']++;
for( int j = 0; j <= K; ++j )
dp[j] = 1;
for( int j = 0; j < i; ++j ) {
for( int k = K; k >= 0; --k ) {
dp[k] = ( !cnt[j][0] || !cnt[j][1] ) ? dp[k] : 0;
if( k >= cnt[j][0] && cnt[j][0] ) dp[k] += dp[k-cnt[j][0]];
if( k >= cnt[j][1] && cnt[j][1] ) dp[k] += dp[k-cnt[j][1]];
if( dp[k] > mod ) dp[k] -= mod;
}
}
p[i] = dp[K];
for( int j = 1; j < i; ++j ) {
if( i % j == 0 ) p[i] = p[i] + mod - p[j];
if( p[i] > mod ) p[i] -= mod;
}
periodic += p[i];
if( periodic >= mod ) periodic -= mod;
}
int total = 0;
for( int i = 0; i <= K; ++i ) {
total += c[N][i];
if( total >= mod ) total -= mod;
}
int Sol = total - periodic + mod;
if( Sol >= mod ) Sol -= mod;
printf( "%d\n", Sol );
}
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Solution implements Runnable {
// leave empty to read from stdin/stdout
private static final String TASK_NAME_FOR_IO = "";
// file names
private static final String FILE_IN = TASK_NAME_FOR_IO + ".in";
private static final String FILE_OUT = TASK_NAME_FOR_IO + ".out";
BufferedReader in;
PrintWriter out;
StringTokenizer tokenizer = new StringTokenizer("");
public static void main(String[] args) {
new Solution().run();
}
final long MOD = 1000000007L;
int N_MAX = 1005;
long[][] cnk = new long[N_MAX][N_MAX];
private void solve() throws IOException {
for (int n = 0; n < N_MAX; n++) {
cnk[n][0] = 1;
cnk[n][n] = 1;
for (int k = 1; k < n; k++) {
cnk[n][k] = cnk[n - 1][k - 1] + cnk[n - 1][k];
cnk[n][k] %= MOD;
}
}
/*
System.out.println("int[][] COEFF = new int[][] {");
for (int n = 0; n <= 1000; n++) {
fastPrecalc(n);
}
System.out.println("};");
*/
/*
Random r = new Random();
for (int n = 1; n <= 50; n++) {
System.out.println("N=" + n);
for (int d = 0; d <= 4; d++)
for (int attempts = 0; attempts < 20; attempts++) {
long mask = r.nextLong() & (1L << 3);
String maskC = "";
long num = mask;
for (int j = 0; j < n; j++) {
maskC += num & 1;
num >>= 1;
}
long a = naive(n, d, maskC.toCharArray());
long b = fast(n, d, maskC.toCharArray());
if (a != b) {
System.err.println(n + " - " + d + " - " + maskC + "(" + a + " vs. " + b + ", delta " + (a - b) + ")");
}
}
}
for (int n = 1; n <= 1000; n++) {
String maskC = "";
for (int j = 0; j < n; j++) {
maskC += "1";
}
long b = fast(n, 0, maskC.toCharArray());
if (b > 0) {
System.err.println(n + " - " + b);
}
}
*/
int tc = nextInt();
for (int tcIdx = 0; tcIdx < tc; tcIdx++) {
int n = nextInt();
int maxD = nextInt();
char[] c = nextToken().toCharArray();
out.println(fast(n, maxD, c));
}
}
static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
static int MAX_GCD_NUM = 1005;
static int[][] GCD_STATIC = new int[MAX_GCD_NUM][MAX_GCD_NUM];
static {
for (int i = 0; i < MAX_GCD_NUM; i++)
for (int j = 0; j <= i; j++) {
int g = gcd(i, j);
GCD_STATIC[i][j] = g;
GCD_STATIC[j][i] = g;
}
}
@SuppressWarnings({"UnusedDeclaration"})
private long notFastEnough(int n, int maxD, char[] c) {
int cnt = 0;
for (int period = 1; period < n; period++) {
if (n % period == 0) {
cnt++;
}
}
int[] periods = new int[cnt];
{
int idx = 0;
for (int period = 1; period < n; period++)
if (n % period == 0) {
periods[idx++] = period;
}
}
long[] periodicAnswer = new long[n];
for (int i = 0; i < cnt; i++) {
periodicAnswer[periods[i]] = countPeriodic(n, maxD, periods[i], c);
}
// calculate total
long total = 0;
for (int i = 0; i <= maxD; i++) {
total += cnk[n][i];
total %= MOD;
}
// calculate partial gcd
int lBits = cnt / 2;
int lBits2 = 1 << lBits;
int[] lGcd = new int[lBits2];
{
for (int mask = 0; mask < lBits2; mask++) {
int common = -1;
for (int i = 0; i < lBits; i++)
if ((mask & (1 << i)) != 0) {
common = (common == -1) ? periods[i] : GCD_STATIC[common][periods[i]];
if (common == 1) {
break;
}
}
lGcd[mask] = common;
}
}
int rBits = cnt - lBits;
int rBits2 = 1 << rBits;
int[] rGcd = new int[rBits2];
{
for (int mask = 0; mask < rBits2; mask++) {
int common = -1;
for (int i = 0; i < rBits; i++)
if ((mask & (1 << i)) != 0) {
common = (common == -1) ? periods[i + lBits] : GCD_STATIC[common][periods[i + lBits]];
if (common == 1) {
break;
}
}
rGcd[mask] = common;
}
}
long cnt2 = 1L << cnt;
for (long mask = 1; mask < cnt2; mask++) {
// determine sign by the number of bits in the mask
int sign = (bitCount(mask) & 1) == 0 ? 1 : -1;
// fast calculate gcd by analysing left and right part
int gcdLeft = lGcd[(int) (mask & (lBits2 - 1))];
int gcdRight = rGcd[(int) (mask >> lBits)];
int common;
if (gcdLeft == -1) {
common = gcdRight;
} else if (gcdRight == -1) {
common = gcdLeft;
} else {
common = GCD_STATIC[gcdLeft][gcdRight];
}
/*
int common = -1;
for (int i = 0; i < cnt; i++)
if ((mask & (1 << i)) != 0) {
common = (common == -1) ? periods[i] : GCD_STATIC[common][periods[i]];
if (common == 1) {
break;
}
}
*/
total += sign * periodicAnswer[common];
total %= MOD;
}
total %= MOD;
total += MOD;
total %= MOD;
return total;
}
private long fast(int n, int maxD, char[] c) {
int cnt = 0;
for (int period = 1; period < n; period++) {
if (n % period == 0) {
cnt++;
}
}
int[] periods = new int[cnt];
{
int idx = 0;
for (int period = 1; period < n; period++)
if (n % period == 0) {
periods[idx++] = period;
}
}
long[] periodicAnswer = new long[n];
for (int i = 0; i < cnt; i++) {
periodicAnswer[i] = countPeriodic(n, maxD, periods[i], c);
}
// calculate total
long total = 0;
for (int i = 0; i <= maxD; i++) {
total += cnk[n][i];
total %= MOD;
}
int[] coeff = COEFF[n];
if (coeff.length != cnt) {
throw new IllegalStateException("INVALID STATE");
}
for (int i = 0; i < cnt; i++) {
total += coeff[i] * periodicAnswer[i];
total %= MOD;
}
total %= MOD;
total += MOD;
total %= MOD;
return total;
}
int[][] COEFF = new int[][] {
{},
{},
{-1,},
{-1,},
{0,-1,},
{-1,},
{1,-1,-1,},
{-1,},
{0,0,-1,},
{0,-1,},
{1,-1,-1,},
{-1,},
{0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,-1,},
{-1,},
{0,0,1,-1,-1,},
{-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,1,0,-1,-1,},
{0,-1,},
{1,-1,-1,},
{0,0,-1,},
{0,1,-1,0,-1,},
{-1,},
{-1,1,1,1,-1,-1,-1,},
{-1,},
{0,0,0,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,1,0,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,1,-1,0,-1,},
{0,1,0,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,0,0,1,0,-1,-1,},
{0,-1,},
{0,0,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{-1,},
{0,0,0,0,1,-1,-1,},
{1,-1,-1,},
{0,0,1,0,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,-1,0,1,0,1,1,-1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{0,1,0,-1,-1,},
{0,0,0,0,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{0,0,1,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,0,1,0,-1,0,-1,},
{0,0,0,-1,},
{1,-1,-1,},
{-1,},
{0,-1,0,1,1,0,-1,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{-1,},
{0,0,-1,0,1,1,0,1,-1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,1,0,-1,-1,},
{-1,},
{0,0,1,-1,-1,},
{0,1,-1,0,-1,},
{0,0,0,0,1,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,1,-1,0,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,1,0,-1,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,1,0,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,-1,0,0,1,0,1,0,1,-1,0,-1,-1,},
{0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,0,-1,},
{0,0,-1,1,0,1,0,-1,1,-1,-1,},
{-1,},
{0,0,0,0,0,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,-1,0,1,1,0,-1,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,1,0,-1,-1,},
{0,0,1,-1,0,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,-1,1,0,0,1,1,-1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,-1,},
{0,1,-1,0,-1,},
{-1,},
{0,0,0,-1,0,1,1,1,-1,-1,-1,},
{-1,},
{0,0,1,-1,0,0,-1,},
{0,1,-1,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,1,0,-1,0,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,1,-1,-1,},
{-1,},
{0,1,-1,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,-1,0,0,1,1,0,0,-1,1,0,-1,-1,},
{0,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,-1,0,-1,},
{0,1,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,0,-1,-1,},
{0,0,0,1,0,-1,0,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,0,0,-1,0,0,1,0,1,0,1,-1,0,-1,-1,},
{-1,},
{-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,0,0,1,0,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,0,0,0,1,-1,0,-1,},
{-1,},
{0,0,-1,1,1,0,-1,0,1,-1,-1,},
{-1,},
{0,0,0,0,0,0,1,0,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,0,0,1,0,-1,0,0,-1,},
{1,-1,-1,},
{1,-1,-1,-1,1,-1,1,1,1,1,-1,1,-1,-1,-1,},
{-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,-1,1,0,1,0,-1,1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,0,0,0,1,0,-1,0,-1,},
{0,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{-1,},
{0,0,-1,1,1,0,-1,0,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,0,0,0,-1,0,0,0,1,0,1,0,1,-1,0,-1,-1,},
{-1,},
{0,0,1,-1,-1,},
{0,0,0,0,-1,},
{0,1,-1,0,-1,},
{0,0,1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{1,-1,-1,},
{0,0,0,0,1,-1,-1,},
{-1,},
{0,0,0,0,-1,0,0,1,0,1,0,0,-1,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,0,0,0,0,0,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,-1,1,0,1,0,-1,1,-1,0,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,-1,0,1,0,1,0,-1,0,1,0,-1,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{-1,},
{0,0,0,0,0,-1,0,0,1,1,0,1,-1,-1,-1,},
{-1,},
{0,0,0,1,-1,0,0,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{0,1,0,-1,-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,0,-1,0,0,1,0,0,1,1,0,-1,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,1,-1,0,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
{0,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{-1,},
{0,0,0,0,-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{0,0,1,0,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,-1,0,0,1,0,1,1,-1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,1,-1,0,0,0,-1,},
{1,-1,-1,},
{0,0,-1,1,1,0,-1,0,1,-1,-1,},
{-1,},
{0,-1,1,0,0,1,1,-1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,-1,0,1,1,0,-1,0,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{0,-1,0,0,1,1,1,0,-1,-1,-1,},
{0,1,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
{0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{1,-1,-1,},
{1,-1,-1,-1,1,1,-1,1,1,-1,1,1,-1,-1,-1,},
{-1,},
{0,1,-1,0,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,-1,0,0,1,0,1,0,0,-1,1,0,-1,-1,},
{-1,},
{0,0,1,-1,-1,},
{1,-1,-1,},
{0,-1,1,0,1,0,-1,1,-1,0,-1,},
{1,-1,-1,},
{0,0,-1,1,1,-1,0,0,1,-1,-1,},
{0,0,-1,},
{0,0,1,-1,0,0,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{-1,},
{0,0,-1,0,1,0,1,1,-1,-1,-1,},
{0,0,1,0,-1,0,-1,},
{0,0,0,0,0,1,0,-1,0,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,0,1,-1,0,-1,-1,},
{0,-1,},
{1,-1,-1,},
{0,0,1,-1,-1,},
{0,-1,1,0,0,1,1,-1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,1,-1,0,0,0,-1,},
{0,1,-1,0,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{-1,},
{-1,1,1,1,-1,-1,-1,},
{0,0,0,0,1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{1,-1,-1,},
{0,0,0,0,0,-1,0,1,0,1,0,-1,1,-1,-1,},
{-1,},
{0,-1,1,0,1,0,-1,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,1,-1,0,-1,},
{-1,},
{1,-1,-1,-1,1,1,-1,1,1,-1,1,1,-1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,1,0,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,-1,0,0,1,1,0,0,-1,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,0,0,0,0,1,0,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,-1,0,1,1,0,-1,0,0,1,0,-1,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{0,0,-1,1,1,-1,0,0,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,1,0,-1,0,0,-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{-1,},
{0,1,0,-1,0,-1,0,-1,1,-1,0,1,0,1,1,0,1,-1,1,-1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,0,1,-1,0,0,-1,},
{0,1,0,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,-1,0,1,0,0,1,0,-1,1,0,-1,0,-1,},
{0,0,0,0,1,0,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
{-1,},
{0,0,0,0,0,0,0,-1,0,0,1,1,0,1,-1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,0,0,-1,0,1,1,0,-1,0,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{0,0,1,0,-1,0,-1,},
{0,-1,1,0,1,-1,0,1,-1,0,-1,},
{-1,},
{1,-1,-1,1,-1,-1,1,1,1,1,-1,-1,1,-1,-1,},
{-1,},
{0,0,0,1,-1,0,0,0,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,0,-1,0,1,0,1,0,-1,0,0,1,0,-1,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,0,-1,-1,},
{0,-1,1,0,1,0,-1,1,-1,0,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,1,-1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,0,0,0,1,-1,0,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,1,-1,-1,},
{-1,},
{0,0,1,-1,0,0,-1,},
{1,-1,-1,},
{0,0,0,-1,0,1,1,1,-1,-1,-1,},
{-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,-1,0,1,0,1,1,-1,0,-1,-1,},
{0,0,0,1,-1,0,0,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,0,0,-1,1,0,-1,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,0,1,-1,-1,},
{0,1,-1,0,-1,},
{-1,},
{1,-1,-1,-1,1,1,1,-1,-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,-1,},
{0,0,1,0,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,-1,0,1,0,0,1,0,-1,1,0,-1,0,-1,},
{-1,},
{0,0,-1,1,1,-1,0,0,1,-1,-1,},
{-1,},
{0,1,-1,0,-1,},
{0,0,-1,0,1,0,1,1,-1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,-1,0,0,1,0,1,0,0,-1,0,1,0,-1,-1,},
{0,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,-1,0,-1,},
{0,-1,1,0,1,0,-1,1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,1,0,-1,-1,},
{0,0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,1,-1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,1,0,-1,0,0,0,-1,},
{1,-1,-1,},
{1,-1,-1,1,-1,-1,1,1,1,1,-1,-1,1,-1,-1,},
{-1,},
{0,1,-1,0,-1,},
{0,1,-1,0,-1,},
{0,0,-1,1,0,0,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,-1,0,1,1,0,-1,0,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,-1,0,-1,},
{-1,},
{0,0,-1,1,1,-1,0,0,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,-1,0,0,1,0,0,0,1,1,0,-1,-1,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,1,0,-1,-1,},
{0,0,1,-1,0,0,-1,},
{-1,},
{1,-1,-1,-1,1,1,1,-1,-1,1,1,1,-1,-1,-1,},
{-1,},
{0,-1,1,0,0,1,1,-1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,0,-1,-1,},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
{-1,},
{0,0,1,-1,-1,},
{1,-1,-1,},
{0,-1,1,0,1,-1,0,1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{0,-1,0,1,0,1,1,-1,0,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,-1,0,1,1,0,-1,1,0,-1,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,1,-1,0,0,0,-1,},
{-1,},
{0,0,0,0,-1,0,1,0,1,0,-1,0,1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,1,-1,0,-1,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,-1,0,-1,},
{0,1,-1,0,-1,},
{0,0,1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,0,1,0,-1,0,0,0,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,-1,0,1,0,1,0,-1,0,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,0,-1,0,1,0,0,0,1,1,-1,0,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,-1,1,0,1,-1,0,1,-1,0,-1,},
{0,0,1,0,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,-1,0,0,1,1,0,0,-1,0,0,1,0,-1,-1,},
{0,0,0,-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{0,0,1,0,-1,0,-1,0,0,-1,1,-1,1,0,1,1,1,0,-1,1,-1,-1,-1,},
{-1,},
{0,0,1,-1,0,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{0,1,0,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,-1,0,-1,},
{0,0,0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,-1,1,0,1,0,-1,1,-1,0,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{0,0,-1,1,0,1,0,-1,1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,1,-1,0,0,0,-1,},
{0,1,-1,0,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,1,0,-1,0,-1,-1,0,1,0,1,-1,1,0,1,0,-1,1,1,-1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,0,-1,1,1,-1,0,0,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,0,-1,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,1,0,-1,-1,},
{0,0,0,0,1,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,-1,0,1,0,0,1,0,-1,1,0,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,0,-1,0,1,1,0,-1,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{0,0,0,0,1,-1,-1,},
{1,-1,-1,},
{0,0,0,1,-1,0,0,0,-1,},
{1,-1,-1,},
{1,-1,-1,-1,1,1,1,-1,-1,1,1,1,-1,-1,-1,},
{-1,},
{0,1,-1,0,-1,},
{0,-1,0,1,0,1,1,-1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,-1,0,1,1,-1,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,-1,0,1,0,0,0,1,1,-1,-1,0,-1,},
{-1,},
{0,0,0,0,-1,0,1,0,1,0,-1,0,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,1,0,-1,0,0,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,-1,0,-1,},
{0,0,1,-1,0,0,-1,},
{1,-1,-1,},
{1,-1,-1,1,-1,1,-1,1,1,-1,1,-1,1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,1,0,1,0,0,1,-1,0,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,1,-1,0,-1,},
{0,0,0,0,-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,-1,0,1,0,0,0,1,1,-1,0,-1,0,-1,},
{0,0,0,0,0,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{0,0,0,-1,0,1,1,1,-1,-1,-1,},
{0,0,0,0,1,0,-1,0,0,0,-1,},
{1,-1,-1,},
{0,0,-1,1,1,-1,0,0,1,-1,-1,},
{-1,},
{0,-1,1,0,1,-1,0,1,-1,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,-1,0,1,1,-1,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,-1,1,0,0,1,1,-1,-1,0,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,-1,0,1,1,1,-1,-1,-1,},
{-1,},
{0,0,0,1,-1,0,0,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,0,-1,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,0,-1,0,1,0,0,1,0,-1,1,0,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,-1,0,1,1,0,-1,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,-1,1,-1,1,1,1,1,-1,1,-1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{-1,},
{0,0,-1,1,1,-1,0,0,1,-1,-1,},
{0,1,-1,0,-1,},
{0,0,1,-1,0,0,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,1,0,-1,0,-1,-1,1,0,0,1,-1,1,0,1,-1,0,1,1,-1,0,-1,-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{0,0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,-1,0,0,1,0,1,0,0,-1,0,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,-1,0,-1,},
{-1,},
{1,-1,-1,1,-1,1,-1,1,1,-1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{-1,},
{0,0,0,0,0,0,0,0,0,-1,0,0,1,1,0,1,-1,-1,-1,},
{-1,},
{0,-1,1,0,1,-1,0,1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,-1,0,1,0,1,0,-1,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,-1,0,1,0,1,1,-1,0,-1,-1,},
{0,-1,1,0,1,-1,0,1,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,1,-1,0,0,-1,},
{0,0,-1,0,1,1,0,1,-1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,0,-1,0,1,1,0,-1,0,0,0,1,0,-1,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,1,0,-1,0,0,-1,},
{0,1,0,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,-1,1,0,0,1,1,-1,-1,0,-1,},
{0,0,1,-1,0,0,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,1,0,0,0,-1,0,-1,0,0,-1,0,1,-1,0,0,1,0,1,1,0,1,0,-1,1,-1,0,-1,-1,},
{0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,0,1,-1,-1,},
{0,0,-1,1,1,-1,0,0,1,-1,-1,},
{0,0,1,-1,-1,},
{0,0,0,1,-1,0,0,0,-1,},
{1,-1,-1,},
{0,0,-1,1,0,1,0,-1,1,-1,-1,},
{1,-1,-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{0,-1,0,1,1,0,-1,1,0,-1,-1,},
{0,0,1,-1,0,0,-1,},
{-1,},
{1,-1,-1,1,-1,-1,1,1,1,1,-1,-1,1,-1,-1,},
{-1,},
{0,-1,1,0,1,-1,0,1,-1,0,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,-1,},
{0,-1,1,0,1,-1,0,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,-1,1,1,1,-1,-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{0,1,-1,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,0,0,1,0,-1,-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,-1,0,0,1,0,0,1,0,0,-1,1,0,-1,0,-1,},
{-1,},
{0,0,0,0,0,0,0,0,-1,1,0,1,0,-1,1,-1,-1,},
{-1,},
{0,-1,1,0,0,1,1,-1,-1,0,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,-1,0,1,1,-1,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,0,0,0,1,0,-1,0,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,1,-1,0,-1,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,1,-1,0,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,-1,1,-1,1,1,1,1,-1,1,-1,-1,-1,},
{-1,},
{0,0,0,0,0,-1,0,1,0,1,0,-1,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{0,0,0,0,-1,0,1,1,0,0,-1,0,1,-1,-1,},
{-1,},
{0,0,-1,0,1,0,1,0,-1,0,1,0,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,1,0,-1,-1,0,0,1,-1,0,-1,1,0,1,1,1,0,-1,-1,1,0,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{0,0,0,0,1,0,-1,0,0,0,-1,},
{-1,},
{1,-1,-1,-1,1,1,1,-1,-1,1,1,1,-1,-1,-1,},
{0,1,0,-1,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{0,0,0,0,0,0,0,-1,0,0,1,0,1,0,0,-1,0,0,0,1,0,-1,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,-1,1,0,1,-1,0,1,-1,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,1,-1,0,0,0,-1,},
{0,0,0,0,-1,0,0,1,0,1,1,0,-1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{1,-1,-1,},
{0,0,-1,1,0,1,0,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,-1,0,1,0,0,1,0,-1,1,0,-1,0,-1,},
{-1,},
{0,0,-1,1,1,-1,0,0,1,-1,-1,},
{1,-1,-1,},
{0,1,-1,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,1,-1,0,-1,-1,},
{0,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,1,-1,0,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{1,-1,-1,1,-1,1,1,-1,-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,0,0,0,1,-1,0,0,-1,},
{-1,1,1,1,-1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{-1,},
{0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{1,-1,-1,},
{0,0,-1,0,1,1,0,1,-1,-1,-1,},
{0,0,0,1,-1,0,0,0,-1,},
{-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,0,0,0,0,0,-1,0,1,0,0,1,1,-1,-1,0,-1,},
{0,1,-1,0,-1,},
{1,-1,-1,},
{-1,},
{0,0,0,-1,0,1,1,-1,0,0,0,1,0,-1,-1,},
{1,-1,-1,},
{-1,1,1,1,-1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{0,-1,1,0,0,1,1,-1,-1,0,-1,},
{1,-1,-1,},
{0,0,1,0,-1,-1,0,0,-1,1,0,1,-1,1,0,1,-1,1,0,1,-1,-1,-1,},
{-1,},
{0,0,0,0,1,0,-1,0,0,0,-1,},
{1,-1,-1,},
{-1,1,1,-1,1,-1,-1,},
{1,-1,-1,},
{0,-1,0,1,1,-1,0,1,0,-1,-1,},
{-1,},
{1,-1,-1,},
{0,0,1,-1,0,0,-1,},
{0,0,0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
};
private void fastPrecalc(int n) {
int cnt = 0;
for (int period = 1; period < n; period++) {
if (n % period == 0) {
cnt++;
}
}
int[] periods = new int[cnt];
{
int idx = 0;
for (int period = 1; period < n; period++)
if (n % period == 0) {
periods[idx++] = period;
}
}
if (cnt > 30) {
System.err.println("N = " + n + ", CNT = " + cnt);
}
long cnt2 = 1L << cnt;
long[] coeff = new long[cnt];
for (long mask = 1; mask < cnt2; mask++) {
// determine sign by the number of bits in the mask
int sign = (bitCount(mask) & 1) == 0 ? 1 : -1;
int common = -1;
for (int i = 0; i < cnt; i++)
if ((mask & (1L << i)) != 0) {
common = (common == -1) ? periods[i] : gcd(common, periods[i]);
if (common == 1) {
break;
}
}
int j = -1;
for (int i = 0; i < cnt; i++)
if (periods[i] == common) {
j = i;
break;
}
coeff[j] += sign;
}
System.out.print(" {");
for (int i = 0; i < cnt; i++) {
System.out.print(coeff[i] + ",");
}
System.out.println("},");
}
private long countPeriodic(int n, int maxD, int period, char[] c) {
int[] zeroes = new int[period];
int[] ones = new int[period];
for (int i = 0; i < period; i++) {
int j = i;
while (j < n) {
if (c[j] != '0') {
ones[i]++;
} else {
zeroes[i]++;
}
j += period;
}
}
long[][] d = new long[period + 1][maxD + 1];
d[0][maxD] = 1;
for (int i = 0; i < period; i++)
for (int remD = 0; remD <= maxD; remD++)
if (d[i][remD] > 0) {
// replace zeroes with ones
if (remD - zeroes[i] >= 0) {
d[i + 1][remD - zeroes[i]] += d[i][remD];
d[i + 1][remD - zeroes[i]] %= MOD;
}
// replace ones with zeroes
if (remD - ones[i] >= 0) {
d[i + 1][remD - ones[i]] += d[i][remD];
d[i + 1][remD - ones[i]] %= MOD;
}
}
long result = 0;
for (int i = 0; i <= maxD; i++) {
result += d[period][i];
result %= MOD;
}
return result;
}
@SuppressWarnings({"UnusedDeclaration"})
private long naive(int n, int maxD, char[] c) {
return naive3(n, maxD, toMask(c));
}
private boolean isPeriodic(int n, long mask) {
for (int period = 1; period < n; period++)
if (n % period == 0 && isPeriodic(n, mask, period)) {
return true;
}
return false;
}
private boolean isPeriodic(int n, long mask, int period) {
for (int i = 0; i < period; i++) {
boolean bitHere = (mask & (1L << i)) != 0;
int j = i;
while (j < n) {
boolean bitThere = (mask & (1L << j)) != 0;
if (bitHere != bitThere) {
return false;
}
j += period;
}
}
return true;
}
@SuppressWarnings({"UnusedDeclaration"})
private long naive1(int n, int maxD, long c) {
long result = 0;
long n2 = 1 << n;
for (long mask = 0; mask < n2; mask++) {
if (distinctBits(n, mask, c) <= maxD && !isPeriodic(n, mask)) {
result++;
}
}
return result;
}
@SuppressWarnings({"UnusedDeclaration"})
private long naive2(int n, int maxD, long c) {
Set<Long> periodic = new HashSet<Long>();
// count only periodic
for (int periodLength = 1; periodLength < n; periodLength++)
if (n % periodLength == 0) {
int periodTimes = n / periodLength;
// brute force period mask
long p2 = 1L << periodLength;
for (long pMask = 0; pMask < p2; pMask++) {
// calculate overall mask
long totalMask = 0;
for (int i = 0; i < periodTimes; i++) {
totalMask <<= periodLength;
totalMask |= pMask;
}
// see if it is applicable
if (distinctBits(n, totalMask, c) <= maxD) {
periodic.add(totalMask);
}
}
}
int total = 0;
for (int k = 0; k <= maxD; k++) {
total += cnk[n][k];
}
return total - periodic.size();
}
private long naive3(int n, int maxD, long c) {
long total = 0;
for (int k = 0; k <= maxD; k++) {
total += cnk[n][k];
}
return total - periodicGen(0, n, maxD, c);
}
private long periodicGen(int pos, int n, int maxD, long c) {
if (pos >= n) {
return isPeriodic(n, c) ? 1 : 0;
}
long total = periodicGen(pos + 1, n, maxD, c);
if (maxD > 0) {
total += periodicGen(pos + 1, n, maxD - 1, c ^ (1L << pos));
}
return total;
}
static int BIT_COUNT_LIMIT_POW = 18;
static int BIT_COUNT_LIMIT_MASK = (1 << BIT_COUNT_LIMIT_POW) - 1;
static int[] BIT_COUNT = new int[1 << BIT_COUNT_LIMIT_POW];
static {
for (int i = 1; i < BIT_COUNT.length; i++)
BIT_COUNT[i] = BIT_COUNT[i & (i - 1)] + 1;
}
@SuppressWarnings({"UnusedParameters"})
private int distinctBits(int n, long m1, long m2) {
return bitCount(m1 ^ m2);
}
private int bitCount(long mask) {
return BIT_COUNT[(int) (mask & BIT_COUNT_LIMIT_MASK)] + BIT_COUNT[(int) ((mask >> BIT_COUNT_LIMIT_POW) & BIT_COUNT_LIMIT_MASK)];
}
private long toMask(char[] c) {
long result = 0;
for (char v : c) {
result <<= 1;
result += v - '0';
}
return result;
}
public void run() {
long timeStart = System.currentTimeMillis();
boolean fileIO = TASK_NAME_FOR_IO.length() > 0;
try {
if (fileIO) {
in = new BufferedReader(new FileReader(FILE_IN));
out = new PrintWriter(new FileWriter(FILE_OUT));
} else {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(new OutputStreamWriter(System.out));
}
solve();
in.close();
out.close();
} catch (IOException e) {
throw new IllegalStateException(e);
}
long timeEnd = System.currentTimeMillis();
if (fileIO) {
System.out.println("Time spent: " + (timeEnd - timeStart) + " ms");
}
}
private String nextToken() throws IOException {
while (!tokenizer.hasMoreTokens()) {
String line = in.readLine();
if (line == null) {
return null;
}
tokenizer = new StringTokenizer(line);
}
return tokenizer.nextToken();
}
private int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
}
Python 3 rep HackerRank Solution
Python 2 rep HackerRank Solution
import math
MODULUS = 1000000007
def countFact(n,p):
k=0
while n>=p:
k+=n/p
n/=p
return k
def pow(a,b,MOD):
x=1
y=a
while b > 0 :
if b%2 == 1:
x=(x*y);
if(x>MOD):
x%=MOD;
y = (y*y);
if(y>MOD): y%=MOD
b /= 2;
return x;
# Modular Multiplicative Inverse
# Using Euler's Theorem
# a^(phi(m)) = 1 (mod m)
# a^(-1) = a^(m-2) (mod m)
def InverseEuler(n,MOD):
return pow(n,MOD-2,MOD);
def factMOD(n,MOD):
res = 1;
while (n > 0):
iter=2
m=n%MOD
while iter<=m:
res = (res * iter) % MOD;
iter=iter+1
n=n/MOD
if (n%2 > 0):
res = MOD - res;
return res;
def C(n,r,MOD):
if (countFact(n, MOD) > countFact(r, MOD) + countFact(n-r, MOD)):
return 0;
return (factMOD(n, MOD) *
((InverseEuler(factMOD(r, MOD), MOD) *
InverseEuler(factMOD(n-r, MOD), MOD)) % MOD)) % MOD;
def binomial(n, k):
if not 0 <= k <= n:
return 0
if k == 0 or k == n:
return 1
P = k+1
for i in xrange(k+2, n+1):
P *= i
return P/math.factorial(n-k)
def numSubsets(arr,sumN):
if sumN == 0:
return 0;
if sumN < 0:
return 0;
a = [[0]*sumN for x in xrange(len(arr)+1)]
for i in range(sumN):
a[0][i] = 1
for i in range(1,len(arr)+1):
for j in range(sumN):
if j-arr[i-1] >= 0 :
a[i][j] = (a[i-1][j] + a[i-1][j-arr[i-1]])%MODULUS
else:
a[i][j] = a[i-1][j]
return a[len(arr)][sumN-1]
t = input()
for i in range(t):
inp = raw_input()
arr = inp.split()
n = int(arr[0])
k = int(arr[1])
stringTransmit = raw_input()
bigsome = 0
periods = [0]
for period in range(1,n):
if n%period != 0:
periods.append(0)
continue
else:
subsetBag = []
tempK= k
for j in range(period):
numzeroes = 0
pointer = j
while pointer < n:
if stringTransmit[pointer] == '0':
numzeroes=numzeroes + 1
pointer = pointer + period
numones = n/period - numzeroes
if (numzeroes<numones):
tempK = tempK - numzeroes
subsetBag.append(numones - numzeroes)
else:
tempK = tempK - numones
subsetBag.append(numzeroes - numones)
numSub = numSubsets(subsetBag,tempK+1)
for iter in range(1,period):
if period%iter==0:
numSub = numSub - periods[iter]
bigsome = (bigsome + numSub)% MODULUS
periods.append(numSub)
allReachable = 1
val = 1
for i in range(1,k+1):
val = ((val*(n-(i-1)))*InverseEuler(i,MODULUS))%MODULUS
allReachable = (allReachable + val)%MODULUS
print (allReachable-bigsome)%MODULUS
C rep HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define DEBUG 0
#if DEBUG
#define TRACE(...) fprintf(stdout, __VA_ARGS__)
#else
#define TRACE(...)
#endif
/*
* Modular arithmetic
*/
#define MOD 1000000007
typedef unsigned long mpz_t;
#define mpz_init(var) __mpz_init(&(var))
#define mpz_clear(var) __mpz_clear(&(var))
#define mpz_set(var, value) __mpz_set(&(var), (value))
#define mpz_set_ui(var, value) __mpz_set_ui(&(var), (value))
#define mpz_add(sum, add1, add2) __mpz_add(&(sum), (add1), (add2))
#define mpz_neg(neg, val) __mpz_neg(&(neg), (val))
#define mpz_sub(diff, sub1, sub2) __mpz_sub(&(diff), (sub1), (sub2))
#define mpz_mul(prod, mul1, mul2) __mpz_mul(&(prod), (mul1), (mul2))
#define mpz_mul_ui(prod, mul1, mul2) __mpz_mul(&(prod), (mul1), (mul2))
#define mpz_pow_ui(res, base, pow) __mpz_pow_ui(&(res), (base), (pow))
#define mpz_ui_pow_ui(res, base, pow) __mpz_ui_pow_ui(&(res), (base), (pow))
#define mpz_inv(inv, val) __mpz_inv(&(inv), val)
#define mpz_div(quot, div, divs) __mpz_div(&(quot), (div), (divs))
#define mpz_bin_uiui(res, n, m) __mpz_bin_uiui(&(res), (n), m)
void __mpz_init(mpz_t *var)
{
*var = 0;
}
void __mpz_clear(mpz_t *var)
{
*var = 0;
}
void __mpz_set(mpz_t *var, mpz_t value)
{
*var = value;
}
void __mpz_set_ui(mpz_t *var, unsigned long int value)
{
*var = value % MOD;
}
void __mpz_add(mpz_t *sum, mpz_t add1, mpz_t add2)
{
*sum = (add1 + add2);
if (*sum >= MOD) *sum -= MOD;
}
void __mpz_neg(mpz_t *neg, mpz_t val)
{
*neg = MOD - val;
}
void __mpz_sub(mpz_t *diff, mpz_t sub1, mpz_t sub2)
{
mpz_t tmp;
mpz_neg(tmp, sub2);
__mpz_add(diff, sub1, tmp);
}
void __mpz_mul(mpz_t *prod, mpz_t mul1, mpz_t mul2)
{
unsigned long long tmp = (mul1 * mul2);
if (tmp >= MOD) tmp %= MOD;
*prod = (mpz_t)tmp;
}
void __mpz_mul_ui(mpz_t *prod, mpz_t mul1, unsigned long mul2)
{
unsigned long long tmp = (mul1 * mul2);
if (tmp >= MOD) tmp %= MOD;
*prod = (mpz_t)tmp;
}
void __mpz_pow_ui(mpz_t *res, mpz_t base, unsigned long pow)
{
unsigned long long tmp = 1;
unsigned long long a = base;
while (pow) {
if (pow & 1) {
tmp *= a;
if (tmp >= MOD) tmp %= MOD;
pow --;
} else {
a *= a;
if (a >= MOD) a %= MOD;
pow >>=1;
}
}
*res = tmp;
}
void __mpz_ui_pow_ui(mpz_t *res, unsigned long base, unsigned long pow)
{
mpz_t tmp;
mpz_set_ui(tmp, base);
__mpz_pow_ui(res, tmp, pow);
}
void __mpz_inv(mpz_t *inv, mpz_t val)
{
__mpz_pow_ui(inv, val, MOD-2);
}
void __mpz_div(mpz_t *quot, mpz_t div, mpz_t divs)
{
mpz_t tmp;
__mpz_inv(&tmp, divs);
__mpz_mul(quot, div, tmp);
}
#define MAX_NM 1024
void __mpz_bin_uiui(mpz_t *res, unsigned long n, unsigned long m)
{
unsigned long long numer;
unsigned long long denom;
unsigned long i;
static mpz_t cache[MAX_NM][MAX_NM];
if (n < MAX_NM && m < MAX_NM && cache[n][m]) {
*res = cache[n][m];
return;
}
numer = 1;
denom = 1;
if (m > n/2) {
for (i = m + 1; i <= n; i++) {
numer *= i;
if (numer >= MOD * 1000ULL) numer %= MOD;
}
for (i=1; i <= (n - m); i++) {
denom *= i;
if (denom >= MOD * 1000ULL) denom %= MOD;
}
} else {
for (i = n - m + 1; i <= n; i++) {
numer *= i;
if (numer >= MOD * 1000ULL) numer %= MOD;
}
for (i=1; i <= m; i++) {
denom *= i;
if (denom >= MOD * 1000ULL) denom %= MOD;
}
}
numer %= MOD;
denom %= MOD;
__mpz_div(res, numer, denom);
if (n < MAX_NM && m < MAX_NM) {
cache[n][m] = *res;
}
}
void
array_print(int n, const int *a)
{
int i;
TRACE("[");
if (n > 0) {
TRACE("%d", a[0]);
for (i = 1; i < n; i++) {
TRACE(", %d", a[i]);
}
}
TRACE("]\n");
}
void
run_print(int n_runs, const int runs[], const int counts[])
{
int i;
TRACE("[");
if (n_runs > 0) {
TRACE("%dx%d", runs[0], counts[runs[0]]);
for (i = 1; i < n_runs; i++) {
TRACE(", %dx%d", runs[i], counts[runs[i]]);
}
}
TRACE("]\n");
}
void
repr_print(int n_runs, const int repr[], const int runs[])
{
int i;
int first = 1;
for (i = 0; i < n_runs; i++) {
if (repr[i]) {
if (first) {
TRACE("%dx%d", runs[i], repr[i]);
first = 0;
} else {
TRACE(" + %dx%d", runs[i], repr[i]);
}
}
}
TRACE("\n");
}
int int_asc(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int int_desc(const void *a, const void *b)
{
return *(int *)b - *(int *)a;
}
/* Create an list of all divisors of the number n, not exceeding n */
int *
get_periods(int n, int *n_divisors)
{
int *divisors;
int max_divisors = ceil(sqrt(n)) * 2;
int i, d, r;
divisors = malloc(max_divisors * sizeof(int));
if (divisors == NULL) {
TRACE("Not enough memory for divisors\n");
return divisors;
}
memset(divisors, 0, max_divisors * sizeof(int));
divisors[0] = 1;
*n_divisors = 1;
for (i = 2; i < n; i++) {
d = n / i;
r = n % i;
if ( d < i ) break; /* We are past sqrt(n) */
if ( r ) continue; /* Not a dvisor */
divisors[(*n_divisors)++] = i;
if ( d > i ) {
divisors[(*n_divisors)++] = d;
}
}
qsort(divisors, *n_divisors, sizeof(int), int_asc);
TRACE("Divisors: ");
array_print(*n_divisors, divisors);
return divisors;
}
int *
compute_diffs(int n, const int *m, int p,
int *min_flips, int *max_flips)
{
int i, j, np;
int ones, zeroes;
int *diffs;
diffs = malloc(p * sizeof(int));
if (diffs == NULL) {
return diffs;
}
np = n / p;
*min_flips = 0;
*max_flips = 0;
/* Get the counts */
for (i = 0; i < p; i++) {
ones = 0;
for (j = i; j < n; j += p) {
ones += m[j];
}
zeroes = np - ones;
if (ones < zeroes) {
*min_flips += ones;
*max_flips += zeroes;
diffs[i] = zeroes - ones;
} else {
*min_flips += zeroes;
*max_flips += ones;
diffs[i] = ones - zeroes;
};
}
TRACE("Distance: %d..%d (%d)\n",
*min_flips, *max_flips, *max_flips - *min_flips);
TRACE("Flip Counts (raw): ");
array_print(p, diffs);
return diffs;
}
/*
* Compress the array of diffs (increments) using RLE.
* runs[i] is a sorted (in descending order) list of all different values
* from diff[]
* count[run[i]] contains the number of given elements in diff[]
* sums[i] contains the sum of runs[j]*count[runs[j]] for j = i..n_runs
*/
int
compress_diffs(int p, int *diffs, int **runs, int **counts, int **sums)
{
int n_runs;
int i;
int last_sum;
/* Sort flip counts in descending order */
qsort(diffs, p, sizeof(int), int_desc);
*runs = malloc(p * sizeof(int));
*sums = malloc(p * sizeof(int));
*counts = malloc((diffs[0] + 1) * sizeof(int));
if ((*runs == NULL) || (*sums == NULL) || (*counts == NULL)) {
return -1;
}
memset(*counts, 0, sizeof(int) * (diffs[0] + 1));
n_runs = 1;
(*runs)[0] = diffs[0];
(*counts)[diffs[0]] = 1;
/* RLE Compression */
for (i = 1; i < p; i++) {
if (diffs[i] == (*runs)[n_runs-1]) {
(*counts)[diffs[i]]++;
} else {
(*runs)[n_runs] = diffs[i];
(*counts)[diffs[i]] = 1;
n_runs++;
}
}
/* Computing the sums of the runs */
last_sum = 0;
for (i = n_runs-1; i >= 0; i--) {
last_sum += (*runs)[i] * (*counts)[(*runs)[i]];
(*sums)[i] = last_sum;
}
TRACE("Compressed diffs: %d runs\n", n_runs);
for (i = 0; i < n_runs; i++) {
TRACE("[%d: %d] (%d)\n",
(*runs)[i], (*counts)[(*runs)[i]], (*sums)[i]);
}
return n_runs;
}
/*
* Get the first representaiton of the number n
*
* Return TRUE if success, 0 if failure
*/
int
get_first(int n, int n_runs,
const int runs[],
const int counts[],
const int sums[],
int repr[])
{
int max_n;
int rem;
int i, j;
int do_trace = 0;
/* If n is bigger the sum of all the elements, no way */
if (n > sums[0]) {
if (do_trace) {
TRACE("%d is too big for ", n);
run_print(n_runs, runs, counts);
}
return 0;
}
/*
* Opitmization in case of 1 element.
* It must be the multiple of runs[0] and less than or equal to
* runs[0] * counts[runs[0]]
*/
if (n_runs == 1) {
if (n % runs[0] == 0) {
if (n / runs[0] <= counts[runs[0]]) {
repr[0] = n / runs[0];
if (do_trace) {
TRACE("%d = ", n);
repr_print(n_runs, repr, runs);
}
return 1;
} else {
/* Would be OK, but the number's too big, We should not
* be getting there, due to the check n > sums[0] above */
if (1) {
TRACE("****** %d cannot be represented using ", n);
run_print(n_runs, runs, counts);
}
return 0;
}
} else {
/* Unfortunately, that was the only option */
if (do_trace) {
TRACE("%d cannot be represented using ", n);
run_print(n_runs, runs, counts);
}
return 0;
}
}
/* Start from the biggest value and attempt to go down */
for (i = 0; i < n_runs; i++) {
max_n = n / runs[i];
if (counts[runs[i]] < max_n) {
max_n = counts[runs[i]];
}
for (j = max_n; j > 0; j--) {
rem = n - runs[i] * j;
if (rem == 0) {
/* The number fit perfectly */
repr[i] = j;
if (do_trace) {
TRACE("%d = ", n); repr_print(n_runs, repr, runs);
}
return 1;
} else {
/* We still have enough smaller elements to try to split rem */
if ((i < n_runs - 1) && (sums[i+1] >= rem)) {
if (get_first(rem, n_runs-i-1,
runs+i+1, counts, sums+i+1, repr+i+1)) {
repr[i] = j;
if (do_trace) {
TRACE("%d = ", n); repr_print(n_runs, repr, runs);
}
return 1;
}
}
}
}
}
if (do_trace) {
TRACE("%d cannot be represented using ", n);
run_print(n_runs, runs, counts);
}
return 0;
}
/*
* Get the first representation of the number n
*
* Return TRUE if success, 0 if failure
*/
int
get_next(int n, int n_runs,
const int runs[],
const int counts[],
const int sums[],
int repr[])
{
int i, j, sum;
int do_trace = 0;
/* If there is only 1 element in runs[], there is no next representation */
if (n_runs > 1) {
sum = runs[n_runs - 1] * repr[n_runs - 1];
repr[n_runs - 1] = 0;
for (i = n_runs - 2; i >= 0; i --) {
for (j = repr[i] - 1; j >= 0; j--) {
/*
* If we can represent sum + runs[i] * j using
* runs[i+1 .. n_runs, that's our next representation
*/
sum += runs[i];
repr[i]--;
if (get_first(sum, n_runs - i - 1,
runs + i + 1, counts, sums + i + 1,
repr + i + 1)) {
if (do_trace) {
TRACE("%d = ", n);
repr_print(n_runs, repr, runs);
}
return 1;
}
}
}
}
TRACE("No more representations for %d\n", n);
return 0;
}
/*
* get_variants: calculate the number of variants for a particular
* representation
*/
void
get_variants(mpz_t *variants, const int repr[],
int n_runs, const int runs[], const int counts[])
{
int i;
mpz_t c;
mpz_set_ui(*variants, 1);
mpz_init(c);
for(i = 0; i < n_runs; i++) {
if (repr[i]) { /* Small optimization for C(0, n) = 1 */
mpz_bin_uiui(c, counts[runs[i]], repr[i]);
mpz_mul(*variants, *variants, c);
}
}
}
/*
* THe REAL Workhorse. Similar to get_number_of_sums but works on a filetered
* set, where runs[0] <= n and runs[n_runs-1] > 0
*
* The idea is to generate the sums in the sorted order.
*
* S1 = a0 + a1 +...+ an, where a[i] >= a[i+1]
* S2 = b0 + b1 +...+ bm, where b[i] >= b[i+1]
*
* S2 follows S1 if for i=0..min(m,n) b[i] <= a[i]
*
* We first generate the "biggest" run, taking as big numbers from runs[] as
* possible (and as many as possible) and then work ourselves up.
*/
int
get_number_of_sums_real(int n, int n_runs,
const int runs[],
const int counts[],
const int sums[],
mpz_t *s_count)
{
int *repr; /* n = runs[0]*repr[0] + ... + runs[n_runs-1]*repr[n_runs-1] */
mpz_t variants;
mpz_init(variants);
mpz_set_ui(*s_count, 0);
repr = malloc(n_runs * sizeof(int));
memset(repr, 0, n_runs * sizeof(int));
if (get_first(n, n_runs, runs, counts, sums, repr)) {
get_variants(&variants, repr, n_runs, runs, counts);
TRACE("First representation for %d = ", n);
repr_print(n_runs, repr, runs);
TRACE("%lu variants for this representation\n", variants);
mpz_add(*s_count, *s_count, variants);
while(get_next(n, n_runs, runs, counts, sums, repr)) {
get_variants(&variants, repr, n_runs, runs, counts);
TRACE("Next representation for %d = ", n);
repr_print(n_runs, repr, runs);
TRACE("%lu variants for this representation\n", variants);
mpz_add(*s_count, *s_count, variants);
}
} else {
TRACE("%d cannot be represented using ", n);
run_print(n_runs, runs, counts);
}
TRACE("TOTAL Variants for %d is %lu\n", n, *s_count);
mpz_clear(variants);
free(repr);
return 0;
}
/*
* Get number of sums.
* Calculate the number of ways a number n can be represented using
* the numbers runs[0]..runs[n_runs-1] when you have counts[runs[i]] of each
*
* The routine will first attempt to reduce the runs by:
* b) eliminating those runs[i] that are greater than n
* c) eliminating cases, where the number cannot be represented
* After that the work is passed to the real routine
*/
int
get_number_of_sums(int n, int n_runs,
const int *runs,
const int *counts,
const int *sums,
mpz_t *s_count)
{
int i;
/* Deal with the case n==0 -- it can be an empty set */
if (n == 0) {
mpz_set_ui(*s_count, 1);
return 0;
}
/* Eliminate runs that are too big */
for (i = 0; i < n_runs; i++) {
if (runs[i] <= n) break;
}
if (i == n_runs) {
TRACE("The smallest element %d > %d\n", runs[n_runs - 1], n);
mpz_set_ui(*s_count, 0);
return 0;
}
if (sums[i] < n) {
TRACE("The sum of suitable elements is %d < %d\n", sums[i], n);
mpz_set_ui(*s_count, 0);
return 0;
}
// TRACE("Using runs %d..%d for number %d\n", i, n_runs-1, n);
get_number_of_sums_real(n, n_runs-i, runs+i, counts, sums+i, s_count);
return 0;
}
int
get_periodics(mpz_t *count, int n, const int *m, int k, int p)
{
int ret = 0;
int min_flips, max_flips;
int i;
int *diffs = NULL;
int *runs= NULL;
int *counts = NULL;
int *sums = NULL;
int n_runs;
mpz_t s_count;
mpz_t zero_mul;
TRACE("\nComputing the periodics for n=%d, p=%d\n", n, p);
mpz_set_ui(*count, 0);
mpz_init(s_count);
mpz_init(zero_mul);
/*
* Compute the max and the min distance to the periodic message,
* as well as the array of possible increments (from min to max)
* The size of the array is always p
*/
diffs = compute_diffs(n, m, p, &min_flips, &max_flips);
if (diffs) {
/* Quick check before we go any further */
if (k >= min_flips) {
/* Compress the runs using RLE */
n_runs = compress_diffs(p, diffs, &runs, &counts, &sums);
if (n_runs > 0) {
/* Deal with zeros (if any) */
mpz_ui_pow_ui(zero_mul, 2, counts[0]);
if (counts[0]) {
n_runs--; /* Forget about zeros */
TRACE("%d zeroes will result in multiplier %lu\n",
counts[0], zero_mul);
}
/*
* Now our task is reduced to figuring out the number of
* ways a number (i - min_flips), where i=0..k
* can be represented as a sum of a subset of nummbers from
* diffs[] (but we'll use the compresed representation)
*/
for (i = 0; i <= k - min_flips; i++) {
get_number_of_sums(i, n_runs, runs, counts, sums, &s_count);
mpz_add(*count, *count, s_count);
}
TRACE("Counts for period %d (no zeroes): %lu\n", p, *count);
mpz_mul(*count, *count, zero_mul);
} else {
ret = -1;
TRACE("Diffs compression failed");
}
} else {
TRACE("No messages with period %d at distance 0..%d\n", p, k);
}
} else {
ret = -1;
TRACE("Could not compute the diffs\n");
}
if (sums) free(sums);
if (counts) free(counts);
if (runs) free(runs);
if (diffs) free(diffs);
mpz_clear(s_count);
mpz_clear(zero_mul);
TRACE("Total count for period %d is %lu\n", p, *count);
return ret;
}
void
remove_duplicate_counts(int n_periods, const int periods[], mpz_t periodics[])
{
int i, j;
int p;
TRACE("\nCounts for periods (with duplicates):\n");
for (i = 0; i < n_periods; i++) {
TRACE("Period %3d: %lu\n", periods[i], periodics[i]);
}
for (i = 0; i < n_periods; i++) {
p = periods[i];
for (j = i + 1; j < n_periods; j++) {
if (periods[j] % p == 0) {
mpz_sub(periodics[j], periodics[j], periodics[i]);
}
}
}
TRACE("\nCounts for periods (without duplicates):\n");
for (i = 0; i < n_periods; i++) {
TRACE("Period %3d: %lu\n", periods[i], periodics[i]);
}
}
void
solve_st(int n, const int *m, int k)
{
int i;
mpz_t mcount, c;
int *periods = NULL; /* Possible values of periods (divisors of n) */
int n_periods; /* Number of possible periods */
mpz_t *periodics = NULL; /* Number of messages with period periods[i] */
/*
* Messages of length 1 are a special case. They are always non-periodic
*/
if (n == 1) {
printf("%d\n", 1<<k);
return;
}
/*
* Calculate the total number of messages within the Hamming sphere
* with the radius k (Hamming distance = 0..k)
*
* k
* -----
* \ i
* > C
* / n
* -----
* i = 0
*/
mpz_init(mcount);
mpz_init(c);
for (i = 0; i <= k; i++) {
mpz_bin_uiui(c, n, i);
TRACE("C(%d, %d) = %lu\n", i, n, c);
mpz_add(mcount, mcount, c);
}
TRACE("Total number of messages: %lu\n", mcount);
periods = get_periods(n, &n_periods);
if (periods == NULL) {
return;
}
periodics = malloc(n_periods * sizeof(mpz_t));
if (periodics == NULL) {
free(periods);
return;
}
/*
* Compute the number of periodic messages within the Hamming Sphere
* of the Radius=k for each of the possible period lengths
*/
for (i = 0; i < n_periods; i++) {
mpz_init(periodics[i]);
if (get_periodics(&(periodics[i]), n, m, k, periods[i])) {
TRACE("Problem computing for period %d\n", periods[i]);
goto cleanup;
}
}
/*
* The values, computed in previous steps are excessive. If p2 = i * p1
* then the counts for p2 include the counts for p1 as well.
* Thus, we need to post_process the counts to remove duplicates
*/
remove_duplicate_counts(n_periods, periods, periodics);
/*
* Now, we need to subtract all these counts from mcount
*/
mpz_set_ui(c, 0);
for (i = 0; i < n_periods; i++) {
mpz_add(c, c, periodics[i]);
}
TRACE("\nTotal number of non-periodic messages:\n%lu - %lu = ", mcount, c);
mpz_sub(mcount, mcount, c);
TRACE("%lu\n==========\n", mcount);
/* Compute the number mod 1000000007 */
printf("%lu\n", mcount);
cleanup:
if (periodics) {
for (i = 0; i < n_periods; i++) {
mpz_clear(periodics[i]);
}
free(periodics);
}
if (periods) free(periods);
mpz_clear(c);
mpz_clear(mcount);
}
void
do_st(void)
{
int n; /* Number of bits in the message */
int *m; /* The message (0's and 1's only) */
int k; /* Max number of errors */
int i;
scanf("%d %d", &n, &k);
if (!((1 <= n) && (n <= 1000))) {
TRACE("Bad message length %d\n", n);
return;
}
if (!((0 <= k) && (k <= n))) {
TRACE("Bad number of corrupt bits %d\n", k);
return;
}
m = malloc(n * sizeof(int));
if (m == NULL) {
TRACE("Out of memory\n");
return;
}
for (i = 0; i < n; i++) {
scanf("%1d", &m[i]);
if (m[i] != 0 && m[i] != 1) {
TRACE("Bad message symbol %d", m[i]);
free(m);
return;
}
}
TRACE("Message: ");
array_print(n, m);
TRACE("K=%d\n", k);
solve_st(n, m, k);
free(m);
}
int
main(int argc, char *argv[])
{
int test_runs;
int t;
scanf("%d", &test_runs);
if (!((1 <= test_runs) && (test_runs <= 20))) {
return 1;
}
for (t = 1; t <= test_runs; t++) {
TRACE("Test run #%d\n"
"============\n", t);
do_st();
}
return(0);
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
