Submission

PPPPPPPPPPP

Score: 100

User: SnowAveNode

Problemset: สุ่มเจาะ

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-20 22:38:00

#include<bits/stdc++.h>
using namespace std;
long long dp[20][11][2];
bool visited[20][11][2];
int D, B;

vector<int> digits;

long long solveDP(int pos, int last, int tight) {
    if (pos == D) return 1;
    
    if (visited[pos][last][tight]) return dp[pos][last][tight];
    visited[pos][last][tight] = true;
    
    long long ways = 0;
    int limit = (tight ? digits[pos] : B - 1);
    
    for (int x = last; x <= limit; x++) {
        int newTight = (tight && (x == limit)) ? 1 : 0;
        ways += solveDP(pos + 1, x, newTight);
    }
    
    dp[pos][last][tight] = ways;
    return ways;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> D >> B;
    string N;
    cin >> N;
    
    digits.resize(D);
    for (int i = 0; i < D; i++){
        digits[i] = N[i] - '0';
    }
    
    memset(visited, 0, sizeof(visited));
    
    long long ans = solveDP(0, 0, 1);
    cout << ans << "\n";
    
    return 0;
}