Submission #2546934


Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <iomanip>
#include <numeric>
#include <functional>
#include <queue>
#include <tuple>
#include <map>

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using ll = long long;
using vll = vector<ll>;
using pii = pair<int, int>;
using vb = vector<char>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;

#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define RREP(i, a, b) for (int i = (int)(b) - 1; i >= a; i--)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, 0, n)
#define all(x) (x).begin(),(x).end()
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define mp(a, b) make_pair(a,b)

#define fi first
#define sn second
#define decpii(p) p.fi--,p.sn--;


#ifdef LOCAL
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define dumpn(c) cerr << "> " << #c << " = " << (c) << ", ";
#else
#define dump(c) ;
#define dumpn(c) ;
#endif


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a) {
    os << '[';
    rep(i, (int) a.size())os << (i ? " " : "") << a[i];
    return os << ']';
}

const int INF = 1 << 29;
const int MOD = 1000000007;

int dxf[] = {1, 0, -1, 0};
int dyf[] = {0, -1, 0, 1};

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

inline vi uni(vi &vec) {
    sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

struct ____ {
    ____() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
    };
} ________;


auto solve() {
    int M;
    string S;
    cin >> M >> S;
    int n = S.length();

    vector<vvi> dp(n + 1, vvi(2, vi(M, 0)));
    dp[0][0][0] = 1;
    rep(i, n) {
        rep(isless, 2) {
            rep(mod, M) {
                int lim = isless ? 9 : S[i] - '0';
                rep(digit, lim + 1) {
                    (dp[i+1][isless || digit < lim][(mod + digit) % M] += dp[i][isless][mod]) %= MOD;
                }
            }
        }
    }

    ll res = 0;
    rep(isless, 2) res += dp[n][isless][0];
    return (res-1) % MOD;
}

int main() {
//    cout << (solve() ? "yes" : "no") << endl;
    cout << solve() << endl;
//    solve();
    return 0;
}

Submission Info

Submission Time
Task E - 数
User palpal
Language C++14 (GCC 5.4.1)
Score 4
Code Size 2862 Byte
Status AC
Exec Time 110 ms
Memory 9088 KB

Judge Result

Set Name All
Score / Max Score 4 / 4
Status
AC × 5
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 AC 2 ms 384 KB
01 AC 67 ms 5888 KB
02 AC 110 ms 9088 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB