Daily PS Comments #2

매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다.

완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요.

 

Special Numbers

링크

mirror 팀에서 cozyyg님의 디버깅 도움으로 AC를 볼 수 있었던 문제입니다. 당시 코드가 굉장히 난잡했어서 깔끔하게 다시 풀어볼 생각입니다.

어제(2023.11.28 - [PS 기록들] - Daily PS Comments #1) 풀었던 문제는 "자릿수 곱이 K 이하인 수의 개수"였고, 이 문제는 "자릿수 곱이 K의 배수인 수의 개수"입니다. 비슷하게 풀어보겠습니다.

 

ㅋㅋㅋㅋ xiaowuc1님이 G1 주신 이유를 알겠네요 이제.. 어제 그 문제랑 똑같이 하되, 곱의 bound를 K로 설정하여 gcd를 관리하면 됩니다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)

#pragma region modnum template from ecnerwala/cp-book
// https://github.com/ecnerwala/cp-book/blob/master/src/modnum.hpp
...
#pragma endregion modnum template
using mint = modnum<1'000'000'007>;

const int N = 23;
int n; ll k;
char s[N];

mint solve(string _s) {
    n = siz(_s);
    rep(i,1,n) s[i] = _s[n-i];
    
    unordered_map<ll,mint> t[N][2], f[N][2]; // k와의 최대공약수
    mint res;
    
    t[0][0][1]=f[0][0][1]=1;
    rep(i,1,n) {
        rep(d,0,9) rep(j,0,1) {
            for (auto &[g,v] : t[i-1][j]) {
                if (d==s[i]-'0') t[i][d>0][gcd(k,g*d)] += v;
            }
            for (auto &[g,v] : f[i-1][j]) {
                f[i][d>0][gcd(k,g*d)] += v;
                if (d<s[i]-'0') t[i][d>0][gcd(k,g*d)] += v;
            }
        }
        if (i < n) res += f[i][1][k];
        else res += t[i][1][k];
    }
    return res;
}

int main() {
    cin >> k;
    
    string L, R;
    cin >> L >> R;
    
    per(i,0,siz(L)-1) {
        if (L[i]=='0') {
            L[i] = '9';
        } else {
            L[i]--;
            break;
        }
    }
    
    while (not empty(L) && L[0]=='0') L.erase(begin(L));
    
    cout << solve(R)-solve(L);
}

 

보일의 법칙

링크

얘도 이제 digit dp 태그입니다.

• 일단 digit-product의 개수가 얼마 없다는 점을 염두에 둡시다.
  • 2-지수 ≤ 3×18, 3-지수 ≤ 2×18, 5-지수 ≤ 18, 7-지수 ≤ 18
  • 가능한 곱의 개수는 629,856가지입니다.
• 각 digit-product $M$에 대해 self-product가 $X$ 이하인 수의 개수는,
  • $\lfloor \frac X M \rfloor$ 이하의 digit-product가 $M$인 수의 개수입니다.
• 정리해봅시다
• (... 대충 digit dp로 해결하기 위한 많은 시행착오)

 

• 아닌듯하다
• 629,856 크기의 digit-dp 집합, $\mathcal{DP}$를 구하는 서브루틴으로 digit dp를 사용했을 가능성이 있습니다.
• $X$ 이하의 digit-product가 $M$인 수의 개수를 굉장히 빠르게 구하는 방법을 고민해보면 좋을 것 같습니다.

 

• 생각이 바뀌었습니다.
• tight와 free를 관리해나가는 것이 digit dp 과정인데,
• 여기서 free한 부분을 미리 전처리해둔다면 tight를 free만 잘 이용해서 빠르게 구성할 수 있지 않을까요?
• 대신 top-down을 해줘야 좋을 것 같습니다.

ac! 숏코딩 1등이네요

#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define siz(x) int((x).size())

const int N = 23;
int n;
char s[N];
unordered_map<ll,ll> f[N];
set<ll> DP;

void precalc() {
    f[0][1]=1;
    rep(i,1,18) rep(d,1,9) {
        for (auto &[j,v] : f[i-1]) {
            if (j*d <= ll(1e18)) {
                f[i][j*d] += v;
                DP.insert(j*d);
            }
        }
    }
}

ll solve(ll x) {
    ll ans = 0;
    for (auto k : DP) {
        string t = to_string(x/k);
        if (t=="0") continue;
        n = siz(t);
        rep(i,1,n) s[i]=t[n-i];
        rep(i,1,n-1) ans += f[i][k];
        per(i,1,n) {
            rep(d,1,min(9,(s[i]-'0'-1))) {
                if (k%d==0) ans += f[i-1][k/d];
            }
            if (s[i]-'0'==0) break;
            if (k%(s[i]-'0')) break;
            k /= s[i]-'0';
            
            if (i==1) ans += k==1;
        }
    }
    return ans;
}

int main() {
    ll A, B;
    cin >> A >> B;
    precalc();
    cout << solve(B)-solve(A-1);
}