This question was asked in Hackwithinfy round 1,2020 which is over now.
can anyone tell me the way to approach this problem?
you are given n , k. and you have to find the sum of all palindromic numbers of size n i.e. no of digits n, which are divisible by k.
constraints:
1<=n<=10^4
1<=k<=100
Are you sure this was the exact question and constraints?
They probably expect a O(nk*base) solution, so the constraints look okay.
Edit : wait, It’s probably mod something
Yeah but this looks unsolvable. Can be solved using digit dp if they want the number of numbers which have their ‘sum of digits’ divisible by k.
In case they want the numbers, we need to touch each n digit palindrome once (which isn’t possible)
sum of numbers mod p is possible.
Let dp[i][j] be the sum of numbers and number of numbers with i digits and are j\ mod\ k.
Now iterate till n/2, and find change in mod k using (10^i + 10^{n-i})\times digit, Find change in sum using number of numbers * (10^i + 10^{n-i})\times digit, except this one is done mod\ p
oh yes,sorry i forgot to mention it was …sum of all palindromic numbers divisible by k mod 10^9+7.
i am facing difficulty in understanding your solution .can you please elaborate.
thank you for helping 
In a palindrome, The digits with place value 10^{i-1} and 10^{n-i} are the same for 0\leq i \leq \lfloor n/2\rfloor. That’s the main observation needed.
Let dp[i][j].first Be the sum of all palindromes, whose First and last i digits are filled, and are j\ mod\ k, and dp[i][j].second be the number of such palindromes.
Now for the dp relation, find the increase if I put the next digit as l, both mod\ k and mod\ p. They are l*(10^{i-1}+10^{n-i}), mod\ k and mod\ p respectively.
Let’s call them valmodk and valmodp.
dp[i][j+valmodk].first=dp[i-1][j].first+dp[i-1][j].second*valmodp
(Obviously j+valmodk \mod k)
The first term is the sum from before, and the second term is the value created when we add a digit l
dp[i][j+valmodk].second=dp[i-1][j].second;
This one is much simpler. the number of ways didn’t increase because we set a digit. It will be overall higher because we’ll set all possible digits 1-10.
Now if it is odd, we need to then iterate over all possibilities for the standalone digit at the end.
It’s a bit difficult, especially to explain it concisely, But you can understand if you try working out the reasoning yourself. Maybe My code will make it clearer?
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
const ll p =1e9 + 7;
ll modpower(ll base, ll power, ll mod=p){
ll ans =1;
base%=mod;
while(power){
if(power&1){
ans*=base;
ans%=mod;
}
base*=base;
base%=mod;
power>>=1;
}
return ans;
}
void solve(){
int n,k;
cin>>n>>k;
vector<vector<pair<ll,ll>>> dp((n/2) + 1, vector<pair<ll,ll>>(k, mp(0,0)));
dp[0][0].second=1;
for(int i=1;i<=(n/2);i++){
for(int j=0;j<k;j++){
for(int l=0;l<10;l++){
if(i==1 && l==0){
continue;
}
ll valmodp=modpower(10, i-1)+modpower(10, n-i);
valmodp*=l;
valmodp%=p;
ll valmodk=modpower(10, i-1, k)+modpower(10, n-i, k);
valmodk*=l;
valmodk%=k;
valmodk+=j;
valmodk%=k;
dp[i][valmodk].first+=dp[i-1][j].first;
dp[i][valmodk].first+=(dp[i-1][j].second*valmodp)%p;
dp[i][valmodk].first%=p;
dp[i][valmodk].second+=dp[i-1][j].second;
dp[i][valmodk].second%=p;
}
}
}
ll ans=0;
if(n&1){
for(int l=0;l<10;l++){
ll valmodp=modpower(10, n/2)*l;
valmodp%=p;
ll valmodk=modpower(10, n/2, k)*l;
valmodk%=k;
valmodk=k-valmodk;
valmodk%=k;
ans+=dp[n/2][valmodk].first;
ans+=dp[n/2][valmodk].second*valmodp;
ans%=p;
}
}
else{
ans=dp[n/2][0].first;
}
cout<<ans<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
Actually this will most likely TLE and you need to compute the powers 10 mod p and mod k before hand, but I don’t have the willpower to actually do it.
Nice DP Approach