Cerinta completa

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.

Constraints



Output Format

Output T lines, one for each test case. Since the answers can be really big, output the numbers modulo 1000000007.

Sample Input 0

3  
5 0  
00000  
3 1  
001  
3 3  
101

Sample Output 0

0
3
6

Explanation 0

Explanation: For the second example, Alice could have transmitted “001”, or “011” or “101”.
For the third example, Alice could have transmitted 001, 010, 100, 011, 101, 110 

Limbajul de programare folosit: cpp14

Cod:

#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);
}

Scor obtinut: 1.0

Submission ID: 464647819

Link challenge: https://www.hackerrank.com/challenges/string-transmission/problem

String Transmission