Gym 100623J Just To Lucky(디지털 dp)

제목: 1-n 중 몇 개의 숫자가 그 자체를 만족시키고 각 수위에 의해 정제될 수 있는지;
사고방식: n은 10의 12차원이다. 곧 디지털 dp라고 생각할 수 있다. 그때는 판자가 없어서 디지털 dp를 어떻게 두드렸는지 잊어버렸다. 나중에 문제풀이를 봤는데 여전히 누드적인 디지털 dp였다.
dp[pos][sum][remain][mod];
pos: 현재 디지털
sum: 각 수위의 합
remain: 현재 열거된 수
mod: 매거막
9*12=108이므로 1-108을 매거하면 됩니다.

#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;
int a[15];
int dp[15][110][110][110];

ll dfs(int pos,int sum,int mod,int remain,bool limit)
{
    if(!pos) return sum==mod&&remain==0;
    if(dp[pos][sum][remain][mod]!=-1&&!limit) return dp[pos][sum][remain][mod];
    int up = limit ? a[pos] : 9;
    ll ans = 0;
    for(int i = 0; i <= up; i++)
    {
        ans += dfs(pos-1,sum+i,mod,(remain*10+i)%mod,limit&&i==up);
    }
    if(!limit)
        dp[pos][sum][remain][mod] = ans;
    return ans;
}

void solve(ll t)
{
    int len = 0;
    while(t)
    {
        a[++len] = t%10;
        t /= 10;
    }
    ll ans = 0;
    for(int i = 1; i <= 108; i++)
    {
        ans += dfs(len,0,i,0,true);
    }
    cout<> m;
    solve(m);

    return 0;
}