网易雷火游戏后台开发笔试
四道编程，很容易就超时。
第三题神奇的数字，我用的回溯，只过了20%。
有没有大佬指点下，实在想不到别的算法。
#include<bits/stdc++.h>
using namespace std;
int N,S,X;
int ans=0,tmp;
void dfs(int idx,int mul,int sum)
{
if(idx>=3)
{
if(mul%X!=0)
return ;
}
if(sum > S)
return;
if(idx>=N)
{
if(sum == S)
{
ans = (ans+1) % 1000009;
}
return ;
}
for(int i=0;i<10;i++)
{
tmp = (mul%100)*10 + i;
dfs(idx+1,tmp,sum+i);
}
}
int main()
{
cin >> N >> S >> X;
dfs(0,0,0);
cout << ans << endl;
return 0;
}
