Submission #74126418

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define endl "\n";
const ll INF = 1e18;
const ll MOD = 998244353;
const int MAXN = 1e6+5;

ll sm(ll num) {
    ll res=0;
    while(num) {
        res+=num%10;
        num/=10;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // int tc;
    // cin >> tc;
    // while (tc--) {
    ll n,m; cin>>n>>m;
    ll k=(m-1)%MOD;
    vector<ll>inv(n+1,0);
    inv[1]=1;
    for (int i=2;i<=n;i++) {
        inv[i]=MOD-(MOD/i)*inv[MOD%i]%MOD;
    }
    vector<ll>b(n+1,0);
    b[0]=1;
    for (int i=1;i<=n;i++) {
        ll sum=0;
        for (int j=1;j<=9;j++) {
            if (j>i) break;
            ll v=(1LL*j*(k+1))%MOD;
            v=(v-i)%MOD;
            if (v<0) v+=MOD;
            sum=(sum+v*b[i-j]%MOD)%MOD;
        }
        b[i]=(sum*inv[i])%MOD;
    }
    ll ans=0;
    for (int i=0;i<=n;i++) {
        ll v=(n-i)/9+1;
        ans=(ans+b[i]*v%MOD)%MOD;
    }
    for (ll i=0;i<n;i++) {
        ll mn=0;
        if (m>=6) {
            mn=sm(i);
        }
        else {
            ll e=pow(10,m-1);
            mn=(i/e)+sm(i%e);
        }
        if (mn<=n && mn%9==n%9) {
            ans=(ans-1+MOD)%MOD;
        }
    }
    cout<<ans<<endl
    // }
}

Submission Info

Judge Result