Expert.
Put your skills to the test.

Problem summary

Count n-digit positive decimal palindromes divisible by p. Leading zeroes are forbidden.

Constraints

1 ≤ n ≤ 15; 1 ≤ p < 10^15.

Worked example

Official statement sample.

5 171

5

Solution analysis

1. A palindrome is determined by h=ceil(n/2) digits. Digit i contributes digit times (10^i+10^(n−1−i)), except that the middle digit of an odd-length number contributes only 10^i. Work with these coefficients modulo p.
2. Split the h independent digits into two groups of at most four. Enumerate all residue sums in each group, excluding zero for digit i=0 because it is also the leading digit. Sort the second list. For every residue r in the first list count occurrences of (p−r) mod p in the second using equal_range.
3. For n=5 the coefficients are 10001,1010,100. Every admissible three-digit choice gives one palindrome; the residue matching selects the five multiples of 171 listed in the statement, including 17271.

Why it works

The mirrored-digit representation is a bijection between allowed digit tuples and n-digit palindromes. Splitting a tuple gives a unique pair of partial residues. Their sum is zero modulo p exactly when the palindrome is divisible by p, and equal_range counts every matching right tuple with its multiplicity.

Watch out. Count repeated residues separately. Do not double the middle digit coefficient or allow the outermost digit to be zero.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long long divisor;
vector<long long>coefficient;
void enumerate(int at,int end,long long residue,vector<long long>&result){
    if(at==end){
        result.push_back(residue);
        return;
    }
    for(int digit=(at==0?1:0);digit<=9;++digit){
        enumerate(at+1,end,(residue+digit*coefficient[at])%divisor,result);
    }
}
int main(){
    int n;
    cin>>n>>divisor;
    vector<long long>power(n,1);
    for(int i=1;i<n;++i){
        power[i]=power[i-1]*10;
    }
    int h=(n+1)/2;
    coefficient.resize(h);
    for(int i=0;i<h;++i){
        coefficient[i]=power[i];
        if(i!=n-1-i){
            coefficient[i]+=power[n-1-i];
        }
        coefficient[i]%=divisor;
    }
    // Match independent half-tuples by complementary residues.
    int split=h/2;
    vector<long long>left,right;
    enumerate(0,split,0,left);
    enumerate(split,h,0,right);
    sort(right.begin(),right.end());
    long long answer=0;
    for(long long residue:left){
        long long need=(divisor-residue)%divisor;
        auto range=equal_range(right.begin(),right.end(),need);
        answer+=range.second-range.first;
    }
    cout<<answer<<'\n';
}