Language: C++

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int M;
int dp[2][2][2][10][500]={};
int num(string s, int rem){
	memset(dp,0,sizeof(dp));
	auto cur=dp[0];
	auto nex=dp[1];
	int order=10%M;
	for(int k=0;k<10;k++){
		cur[0][0][k][k%M]=cur[1][0][k][k%M]=1;
		if(k<=s[0]-'0'){
			cur[0][1][k][k%M]=cur[1][1][k][k%M]=1;
		}
	}
	int ret=0;
	ret/=2;
	ret%=10000;
	for(int i=1;i<s.size();i++){
		for(int k=1;k<10;k++){
			//cout << k << ": " << cur[0][0][k][0] << ", " << cur[1][0][k][0] << endl;
			ret+=cur[0][0][k][rem]+cur[1][0][k][rem];
		}
		if(i==1){
			ret/=2;
		}
		//cout << i << ", " << ret << endl;
		ret%=10000;
		for(int r=0;r<M;r++){
			for(int k=1;k<10;k++){
				cur[0][0][k][r]+=cur[0][0][k-1][r];
				cur[0][0][k][r]%=10000;
				cur[0][1][k][r]+=cur[0][1][k-1][r];
				cur[0][1][k][r]%=10000;
			}
			for(int k=8;k>=0;k--){
				cur[1][0][k][r]+=cur[1][0][k+1][r];
				cur[1][0][k][r]%=10000;
				cur[1][1][k][r]+=cur[1][1][k+1][r];
				cur[1][1][k][r]%=10000;
			}
		}
		for(int k=0;k<10;k++){
			int v=(order*k)%M;
			for(int r=0;r<M;r++){
				if(k>0){
					nex[1][0][k][r]=cur[0][0][k-1][(r-v+M)%M];
					if(k<s[i]-'0'){
						nex[1][1][k][r]=nex[1][0][k][r];
					}
					else if (s[i]-'0'==k)
					{
						nex[1][1][k][r]=cur[0][1][k-1][(r-v+M)%M];
					}
					else
					{
						nex[1][1][k][r]=0;
					}
				}
				else
				{
					nex[1][0][k][r]=0;
					nex[1][1][k][r]=0;
				}
				if(k<9){
					nex[0][0][k][r]=cur[1][0][k+1][(r-v+M)%M];
					if(k<s[i]-'0'){
						nex[0][1][k][r]=nex[0][0][k][r];
					}
					else if(s[i]-'0'==k){
						//cout << "aaa " << k << ": " << v << ", " << cur[1][1][k+1][(r-v+M)%M] << endl;
						nex[0][1][k][r]=cur[1][1][k+1][(r-v+M)%M];
					}
					else
					{
						nex[0][1][k][r]=0;
					}
				}
				else
				{
					nex[0][0][k][r]=0;
					nex[0][1][k][r]=0;
				}
			}
		}
		order*=10;
		order%=M;
		swap(cur,nex);
	}
	for(int k=1;k<=s[s.size()-1]-'0';k++){
		//cout << k << ", " << cur[0][1][k][0] << ", " << cur[1][1][k][0] << endl;
		ret+=cur[0][1][k][rem]+cur[1][1][k][rem];
	}
	if(s.size()==1){
		ret/=2;
	}
	ret%=10000;
	return ret;
}
int num2(string a, int rem){
	reverse(a.begin(),a.end());
	istringstream istr(a);
	int v;
	istr >> v;
	int ret=0;
	for(int i=rem;i<=v;i+=M){
		if(i==0)continue;
		ostringstream ostr;

Compiler output:
a.cc: In function 'int num2(std::string, int)':
a.cc:132:36: error: expected '}' at end of input
  132 |                 ostringstream ostr;
      |                                    ^
a.cc:130:33: note: to match this '{'
  130 |         for(int i=rem;i<=v;i+=M){
      |                                 ^
a.cc:132:36: error: expected '}' at end of input
  132 |                 ostringstream ostr;
      |                                    ^
a.cc:124:28: note: to match this '{'
  124 | int num2(string a, int rem){
      |                            ^
a.cc:132:36: warning: no return statement in function returning non-void [-Wreturn-type]
  132 |                 ostringstream ostr;
      |                                    ^