In this HackerRank String Transmission problem solution, 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.
Problem solution in Python.
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)
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
static final int N = 1001;
static final int MOD = 1_000_000_007;
static int[] getPrimes() {
int[] pr = new int[168];
int[] mu = new int[N];
boolean[] sieved = new boolean[N];
int np = 0;
mu[1] = 1;
for (int i = 2; i < N; i++) {
if (!sieved[i]) {
pr[np++] = i;
mu[i] = -1;
}
for (int j = 0; j < np && i * pr[j] < N; j++) {
sieved[i * pr[j]] = true;
if (i % pr[j] == 0) {
mu[i * pr[j]] = 0;
break;
}
mu[i * pr[j]] = -mu[i];
}
}
return mu;
}
static int[][] getBinomials() {
int[][] binom = new int[N+1][N+1];
for (int i = 0; i <= N; i++) {
binom[i][0] = binom[i][i] = 1;
for (int j = 1; j < i; j++) {
binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
}
}
return binom;
}
static int stringTransmission(int k, char[] a, int n, int[] mu, int[][] binom) {
int[] dp = new int[k+1];
int ans = 0;
for (int i = 2; i <= n; i++) {
if ((n % i) == 0 && mu[i] != 0) {
int m = n / i;
Arrays.fill(dp, 0);
dp[0] = 1;
for (int j = 0; j < m; j++) {
int x = 0;
for (int g = j; g < n; g += m) {
x += a[g] == '1' ? 1 : 0;
}
int y = i - x;
for (int g = k + 1; --g >= 0;) {
dp[g] = ((g < x ? 0 : dp[g - x]) + (g < y ? 0 : dp[g - y])) % MOD;
}
}
long sum = 0;
for (int j = 0; j <= k; j++) {
sum = (sum + dp[j]) % MOD;
}
ans = (int) ((ans + sum * mu[i]) % MOD);
}
}
for (int i = 0; i <= k; i++) {
ans = (ans + binom[n][i]) % MOD;
}
return (ans + MOD) % MOD;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int[] mu = getPrimes();
int[][] binom = getBinomials();
StringTokenizer st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
for (int tItr = 0; tItr < t; tItr++) {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
String s = br.readLine();
int result = stringTransmission(k, s.toCharArray(), n, mu, binom);
bw.write(String.valueOf(result));
bw.newLine();
}
bw.close();
br.close();
}
}
Problem solution in C++.
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std ;
#define add(reg, val) {reg += val ; if (reg >= modul) reg -= modul ; }
int n, k, bin [1001] [1001], modul = 1000000007 ;
int main() {
memset(bin, 0, sizeof(bin)) ;
bin [0] [0] = 1 ;
for (int i = 1 ; i < 1001 ; i ++) {
bin [i] [0] = 1 ;
for (int j = 1 ; j < 1001 ; j ++) {
add(bin [i] [j], bin [i - 1] [j - 1] + bin [i - 1] [j]) ;
}
}
int numTests, dp [1001] [2], c [1001] [2], period [1001] ;
scanf("%d", &numTests) ;
char s [1001] ;
for (int test = 0 ; test < numTests ; test ++) {
scanf("%d%d%s", &n, &k, s) ;
int len = strlen(s), total = 0 ;
for (int kk = 0 ; kk <= k ; kk ++) add(total, bin [n] [kk]) ;
for (int d = 1 ; d < len ; d ++) if (len % d == 0) {
for (int i = 0 ; i < d ; i ++) for (int ch = 0 ; ch <= 1 ; ch ++) c [i] [ch] = 0 ;
int j = 0 ;
for (int i = 0 ; i < len ; i ++) {
c [j] [s [i] - '0'] ++ ;
j ++ ;
if (j >= d) j -= d ;
}
memset(dp, 0, sizeof(dp)) ;
dp [0] [0] = 1 ;
int cur = 0, ncur, rep = n / d ;
for (int i = 0 ; i < d ; i ++) {
ncur = cur ^ 1 ;
for (int j = 0 ; j <= k ; j ++) dp [j] [ncur] = 0 ;
for (int j = 0 ; j <= k ; j ++) if (dp [j] [cur]) {
for (int ch = 0 ; ch <= 1 ; ch ++)
if (j + c [i] [ch] <= k) add(dp [j + c [i] [ch]] [ncur], dp [j] [cur]) ;
}
cur = ncur ;
}
period [d] = 0 ;
for (int i = 0 ; i <= k ; i ++) add(period [d], dp [i] [cur]) ;
for (int dd = 1 ; dd < d ; dd ++) if (d % dd == 0) add(period [d], modul - period [dd]) ;
add(total, modul - period [d]) ;
}
printf("%dn", total) ;
}
return 0 ;
}
Problem solution 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("%dn",(g(N,p)+1000000007)%1000000007);
}
exit(0);
}