Submission #5418760


Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;


LL dp[10005][105][2];

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int D; cin >> D;
    string N; cin >> N;
    memset(dp,0,sizeof(dp));

    dp[0][0][0] = 1;

    for(int pos = 0; pos < int(N.length()); pos++){
        for(int sum = 0; sum < D; sum++){
            for(int sml = 0; sml <= 1; sml++){
                if(!dp[pos][sum][sml]) continue;

                if(sml == 1){
                    REP(d,10){
                        (dp[pos+1][(sum+d)%D][1] += dp[pos][sum][1]) %= MOD;
                    }
                }
                else{
                    int lim = N[pos] - '0';
                    for(int d = 0; d < lim; d++){
                        (dp[pos+1][(sum+d)%D][1] += dp[pos][sum][0]) %= MOD;
                    }

                    (dp[pos+1][(sum+lim)%D][0] += dp[pos][sum][0]) %= MOD;
                }
            }
        }
    }
    cout << (dp[N.length()][0][0]+dp[N.length()][0][1]-1)%MOD << endl;


}

Submission Info

Submission Time
Task E - 数
User Bloody_Yulii
Language C++14 (GCC 5.4.1)
Score 4
Code Size 2333 Byte
Status AC
Exec Time 53 ms
Memory 16640 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 6 ms 16640 KB
01 AC 34 ms 16640 KB
02 AC 53 ms 16640 KB
90 AC 6 ms 16640 KB
91 AC 6 ms 16640 KB