0 like 0 dislike
2,869 views
Given a string of length  , n .

It contains either '?' or a digit from '0' to '9'.

Find the number of possible good strings.

Good strings are numbers which leave remainder 7 when divided by 11 and 13.

1<=n<=10000

Example input 1 :

??756

Output : 1

Only 1 good string is possible which is 34756

Example input 2 :

??33?

Output : 10

Some of the possible strings are : {   42335 , 46339 } . There are 8 more strings which are good strings , i.e , they leave remainder 7 when divided by 11 and 13 individually.

retagged | 2,869 views

0 like 0 dislike

The solution involves dynamic programming(multi-dimensional). Here is my code for the same :----->

```#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ;
ll dp[15][15][10000+5] ;
ll e = 1e9 + 7 ;
int main()
{
string s ;
cin>>s ;
ll n = s.size() ;
dp[0][0][0] = 1 ;
ll i = 1 ;
while(i<=n)
{
if(s[i-1]=='?')
{
ll number = 0 ;
while(number<=9)
{
ll i1 = 0 ;
while(i1<=10){
ll j1 = 0 ;
while(j1<=12)
{
ll x1 = ( (i1%11*10%11)%11 + number%11)%11;
ll y1 = ( (j1%13*10%13)%13 + number%13)%13;
dp[x1][y1][i] = (dp[x1][y1][i] + dp[i1][j1][i-1])%e   ;
j1++;
}
i1++;
}
number++;
}
}
else
{
ll number = int(s[i-1])-48;
ll i1 = 0 ;
while(i1<=10)
{
ll j1 = 0 ;
while(j1<=12)
{
ll x1 = ( (i1%11*10%11)%11 + number%11)%11;
ll y1 = ( (j1%13*10%13)%13 + number%13)%13;
dp[x1][y1][i] = (dp[x1][y1][i] + dp[i1][j1][i-1])%e   ;
j1++;
}
i1++;
}
}
i++;
}
cout<<dp[7][7][n];
return 0 ;
}

```
by Expert (113,040 points)