String Transmission
Problem Statement :
Bob has received a binary string of length N transmitted by Alice. He knows that due to errors in transmission, up to K bits might have been corrupted (and hence flipped). However, he also knows that the string Alice had intended to transmit was not periodic. A string is not periodic if it cannot be represented as a smaller string concatenated some number of times. For example, "0001", "0110" are not periodic while "00000", "010101" are periodic strings. Now he wonders how many possible strings could Alice have transmitted. Input Format The first line contains the number of test cases T. T test cases follow. Each case contains two integers N and K on the first line, and a binary string of length N on the next line. Output Format Output T lines, one for each test case. Since the answers can be really big, output the numbers modulo 1000000007.
Solution :
Solution in C :
In C :
#include <stdlib.h>
#include <stdio.h>
int N,K;
int F[1000][1000],S[1000];
char s[1001];
int f(int x, int i, int j) {
if(j>K) return 0;
if(i==x) return 1;
if(F[i][j]==-1) F[i][j] = (f(x,i+1,j+S[i])+f(x,i+1,j+N/x-S[i]))%1000000007;;
return F[i][j];
}
int g(int x, int *p) {
if((*p)!=0) return (g(x,p+1)-g(x/(*p),p+1))%1000000007;
int i,j;
for(i=0; i<x; i++) for(j=0; j<=K; j++) F[i][j] = -1;
for(i=0; i<x; i++) {
S[i] = 0;
for(j=i; j<N; j+=x) S[i]+= (s[j]=='1')?1:0;
}
return f(x,0,0);
}
int main() {
int i,j,k,T;
int ps[170],l[500],p[5];
for(i=0;i<500;i++) l[i] = 1;
ps[0] = 2;
for(i=3,k=1;i<1000;i+=2) if(l[i/2]) {
ps[k++] = i;
for(j=i*i/2;j<500;j+=i) l[j] = 0;
}
scanf("%d",&T);
for(;T>0;T--) {
scanf("%d %d %[01]",&N,&K,s);
for(i=0,j=0; i<k; i++) if(N%ps[i]==0) p[j++] = ps[i];
p[j] = 0;
printf("%d\n",(g(N,p)+1000000007)%1000000007);
}
exit(0);
}
Solution in C++ :
In C ++ :
#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;
}
Solution in Java :
In Java :
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());
}
}
Solution in Python :
In Python3 :
T = int(input())
M = 1000000007
from math import factorial, sqrt
def nck(n, k):
res = 0
for i in range(k+1):
res += factorial(n)//(factorial(i)*factorial(n-i))
return res
def divisors(n):
d1 = [1]
d2 = []
for i in range(2, int(sqrt(n)) + 1):
if n % i == 0:
d1.append(i)
if i*i != n:
d2.append(n//i)
d1.extend(d2[::-1])
return d1
for _ in range(T):
N, K = [int(x) for x in input().split()]
S = input()
if N == 1:
print(N+K)
continue
total = nck(N, K)
div = divisors(N)
dp = [[0]*(N+K+1) for i in range(len(div))]
is_periodic = False
for i, d in enumerate(div):
dp[i][0] = 1
for offset in range(d):
zeros = 0
for j in range(offset, N, d):
if S[j] == "0":
zeros += 1
ones = N//d - zeros
prev = list(dp[i])
dp[i][:] = [0]*(N+K+1)
for k in range(K+1):
if prev[k]:
dp[i][k + zeros] += prev[k]
dp[i][k + ones] += prev[k]
if dp[i][0]:
is_periodic = True
for i2 in range(i):
d2 = div[i2]
if d % d2 == 0:
for k in range(K+1):
dp[i][k] -= dp[i2][k]
for k in range(1, K+1):
total -= dp[i][k]
print((total-is_periodic) % M)
View More Similar Problems
Subsequence Weighting
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =
View Solution →Kindergarten Adventures
Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti
View Solution →Mr. X and His Shots
A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M
View Solution →Jim and the Skyscrapers
Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently. Let us describe the problem in one dimensional space
View Solution →Palindromic Subsets
Consider a lowercase English alphabetic letter character denoted by c. A shift operation on some c turns it into the next letter in the alphabet. For example, and ,shift(a) = b , shift(e) = f, shift(z) = a . Given a zero-indexed string, s, of n lowercase letters, perform q queries on s where each query takes one of the following two forms: 1 i j t: All letters in the inclusive range from i t
View Solution →Counting On a Tree
Taylor loves trees, and this new challenge has him stumped! Consider a tree, t, consisting of n nodes. Each node is numbered from 1 to n, and each node i has an integer, ci, attached to it. A query on tree t takes the form w x y z. To process a query, you must print the count of ordered pairs of integers ( i , j ) such that the following four conditions are all satisfied: the path from n
View Solution →