The Dividing Path - 2

Well the solution to this problem is pretty easy with dp. Here's the code for the same:

#include <bits/stdc++.h>
#define ll long long
#define FOR(i,a,b) for( ll i = a; i <= b; i++ )
using namespace std;

ll dp[35][40] = {0};

ll rec( ll r, ll rem ) {
    if( r >= 31 )
        return 0;

    ll ans = 0;
    if( rem%37 == 0 )
       ans++;
    if( dp[r][rem] != -1 )
        return dp[r][rem];
    return dp[r][rem] = ans + rec( r+1, ( rem*10 )%37 ) + rec( r+1, ( rem*10 + 1 )%37 );    

}

int main() {

    memset( dp, -1, sizeof dp );
    ll num = rec( 1, 1 );

    cout << num << endl;

    ll sum = 0;
    while( num > 0 ) {
        sum += num%10;
        num /= 10;
    }

    cout << sum << endl;

}

The solution to this problem is easy if you know the solution for part one, The Dividing Path - 1. There is a special trick discovered by Calvin Lin in finding out whether a positive integer is divisible by 37. For more information see the solution of part 1 and (http://www.thirty-seven.org/misc/divisibility.html).

For positive integer $N$ with either $0$ or $1$ as digits, the solution is first to find the $n_0$ number of $1's$ of all the $0\space mod\space 3$ digits of $N$ , $n_1$ of $1\space mod\space 3$ digits, and $n_2$ of $2\space mod\space 3$ digits. Then, if $a = n_0 + 10n_1 + 26n_2$ and $a \equiv 0\space mod\space 37$ or $a$ is divisible by $37$ , then $N$ is divisible by $37$ .

My simple Python script for the problem is:

1. To find $n_0$ , $n_1$ and $n_2$

2. If $a \equiv 0\space mod\space 37$ , the find $S$ the number of $N$ with these specific $n_0$ , $n_1$ and $n_2$ . That is $S = { _{ 10 }{ C }_{ { n }_{ 0 } } }{ _{ 10 }{ C }_{ { n }_{ 1 } } }{ _{ 10 }{ C }_{ { n }_{ 2 } } }$ .

3. Add all the $S$ 's together and then find its digital sum.

from math import factorial as f

def comb10(n): # Computing 10Cn

      x = f(10)/f(n)/f(10-n)

      return x

S = 0

for i in range(1,11):

      for j in range(1,11):

              for k in range(1,11):

                         a = 26*i + 10*j + k

                         if a % 37 == 0:

                                    n = comb10(i)*comb(j)*comb(k)

                                    S += n

                                    print i, j, k, n, S

The answer is $S = 39531459$ and its digital sum is $\boxed{39}$ .