Подсчитайте подпоследовательности длины 4, кратные 9

Если вы хотите проверить, делится ли число на 9, вам лучше посмотреть здесь.

Кратко опишу метод:

checkDividedByNine(String pNum) :
If pNum.length < 1
   return false
If pNum.length == 1
   return toInt(pNum) == 9;
Sum = 0
For c in pNum:
    Sum += toInt(pNum)
return checkDividedByNine(toString(Sum))

Таким образом, вы можете сократить время работы до менее O (n ^ 3).

РЕДАКТИРОВАТЬ: Если вам нужен очень быстрый алгоритм, вы можете использовать предварительную обработку, чтобы сохранить для каждого возможного 4-значного числа, если оно делится на 9. (Это будет стоить вам 10000 памяти)

РЕДАКТИРОВАТЬ 2: лучший подход: вы можете использовать динамическое программирование:

Для строки S длиной N:

D [i, j, k] = количество подпоследовательностей длины j в строке S [i..N], значение которых по модулю 9 == k.

Где 0 ‹= k‹ = 8, 1 ‹= j‹ = 4, 1 ‹= i‹ = N.

D[i,1,k] = simply count the number of elements in S[i..N] that = k(mod 9).
D[N,j,k] = if j==1 and (S[N] modulo 9) == k, return 1. Otherwise, 0.
D[i,j,k] = max{ D[i+1,j,k], D[i+1,j-1, (k-S[i]+9) modulo 9]}.

И вы вернете D [1,4,0].

Получается стол размером - N х 9 х 4.

Таким образом, общее время выполнения, если вычисление по модулю занимает O (1), составляет O (n).

Предполагая, что подпоследовательность должна состоять из последовательных цифр, вы можете сканировать слева направо, отслеживая, в каком порядке читаются последние 4 цифры. Таким образом, вы можете выполнить линейное сканирование и просто применить правила делимости.

Если цифры не обязательно идут подряд, вы можете немного поработать с таблицами поиска. Идея состоит в том, что вы можете создать трехмерный массив с именем table, в котором table[i][j][k] - это количество сумм из i цифр до индекса j, так что сумма оставляет остаток k при делении на 9. Сама таблица имеет размер 45n (i идет от 0 до 4, j от 0 до n-1, а k от 0 до 8).

Для рекурсии каждая table[i][j][k] запись опирается на table[i-1][j-1][x] и table[i][j-1][x] для всех x от 0 до 8. Поскольку каждое обновление записи занимает постоянное время (по крайней мере, относительно n), это должно дать вам время выполнения O (n).

Как насчет этого:

/*NOTE: The following holds true, if the subsequences consist of digits in contagious locations */ 

public int countOccurrences (String s) {
    int count=0;
    int len = s.length();
    String subs = null;
    int sum;

    if (len < 4)
        return 0;
    else {
        for (int i=0 ; i<len-3 ; i++) {
            subs = s.substring(i, i+4);
            sum = 0;

            for (int j=0; j<=3; j++) {
                sum += Integer.parseInt(String.valueOf(subs.charAt(j)));
            }

            if (sum%9 == 0)
                count++;
        }           
        return count;
    }   
}

Вот полный рабочий код для вышеупомянутой проблемы, основанный на описанных выше способах использования таблиц поиска.

int fun(int h)
{
return (h/10 + h%10);
}

int main()
{
int t;
scanf("%d",&t);
int i,T;
for(T=0;T<t;T++)
{
    char str[10001];
    scanf("%s",str);        
    int len=strlen(str);
    int arr[len][5][10];
    memset(arr,0,sizeof(int)*(10*5*len));

    int j,k,l;
        for(j=0;j<len;j++)
            {
              int y;
                y=(str[j]-48)%10;
                arr[j][1][y]++;
            }



        //printarr(arr,len);    





        for(i=len-2;i>=0;i--)   //represents the starting index of the string
            {


                    int temp[5][10];
                    //COPYING ARRAY
                    int a,b,c,d;
                    for(a=0;a<=4;a++)
                    for(b=0;b<=9;b++)
                    temp[a][b]=arr[i][a][b]+arr[i+1][a][b];


            for(j=1;j<=4;j++)   //represents the length of the string
                {
                for(k=0;k<=9;k++)   //represents the no. of ways to make it
                    {

                        if(arr[i+1][j][k]!=0)
                          {
                          for(c=1;c<=4;c++)
                            {
                              for(d=0;d<=9;d++)
                                 {
                            if(arr[i][c][d]!=0)
                                 {
                                int h,r;
                                r=j+c;
                                if(r>4)
                                continue;
                                h=k+d;                      
                                h=fun(h);
                                if(r<=4)
                                  temp[r][h]=( temp[r][h]+(arr[i][c][d]*arr[i+1][j][k]))%1000000007;
                              }}}
                        }






                    //copy back from temp array

                    }
                }
                for(a=0;a<=4;a++)
                    for(b=0;b<=9;b++)
                    arr[i][a][b]=temp[a][b];
            }








printf("%d\n",(arr[0][1][9])%1000000007);


}


    return 0;
}