AtCoder Regular Contest 052 D - 9

問題

D: 9 - AtCoder Regular Contest 052 | AtCoder

解法

愚直解では太刀打ち出来ないが、各桁の総和はせいぜい100もないので、Kで割った余りが0～100くらいまでの数だけを調べるように改善すれば、のアルゴリズムになる。
これはKが大きい時に有効そうなので、Kが小さい時を他のアルゴリズムで倒せないか考える。
それは下のような桁DPで解決できる。
dp[i][j][k][b] = 「{i桁目までが決まった}, {Kで筆算的に計算してきた余りがj}, {各桁の和%Kがj}, {bが0の場合は決めてきた桁がMを超え得る状態であり, 1の場合はそうでない}」という状態の総数。
(日本語が下手)
これは各桁の総和が最大でもSとすると、。

実装

半分全列挙解があるらしい。頭良さそう

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int K, M;
string strM;
int memo[10][1001][1001][2];
 
int DFS(int n, int rem0, int rem1, bool flg)
{
    if (n == strM.size()) return (rem0 == rem1);
    int &_memo = memo[n][rem0][rem1][flg];
    if (_memo != -1) return _memo;
    int res = 0;
    for (int i = 0; i < 10; i++)
    {
        if (flg && strM[n] - '0' < i) break;
        bool nflg = false;
        if (flg && strM[n] - '0' == i) nflg = true;
        res += DFS(n + 1, (rem0*10 + i) % K, (rem1 + i) % K,  nflg);
    }
    return _memo = res;
}
 
int SolveSmall()
{
    //K^2*(Mの桁数)
    fill((int*)memo, (int*)memo + 10*1001*1001*2, -1);
    return DFS(0, 0, 0, true) - 1;
}
 
bool IsOK(int n)
{
    int w = 1, sum = 0;
    for (int i = 0; i < 11; i++, w *= 10)
    {
        sum += (n/w) % 10;
    }
    return (n % K == sum % K);
}
 
int SolveLarge()
{
    //M/K*(Mの桁数)*9
    int ans = 0;
    for (int i = 0; i <= M; i += K)
    {
        for (int j = 0; j < min(90ll, K); j++)
        {
            ans += IsOK(i + j);
        }
    }
    return ans - 1;
}
 
signed main()
{
    cin >> K >> strM;
    stringstream ss(strM);
    ss >> M;
    if (K < 1000) printf("%lld\n", SolveSmall());
    else printf("%lld\n", SolveLarge());
    return 0;
}