Submission #10044807


Source Code Expand

Copy
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}



long long combination(int n, int k){
    static const int maxi = 1e6+1;
    static vector<ll> fac(maxi,0),finv(maxi,0),inv(maxi,0);
    static const int mod = 1e9+7;
    // キャッシュされてない場合COMinit()と同様のことをする。
    if (fac[0]==0) {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < maxi; i++){
            fac[i] = fac[i - 1] * i % mod;
            inv[i] = mod - inv[mod%i] * (mod / i) % mod;
            finv[i] = finv[i - 1] * inv[i] % mod;
        }
    }
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}


string N;
ll K;

// i桁目まで見たとして、残りがk回0以外を入れられていて、未満確定ならsmallerはtrueで答えを出す。
ll solve(ll i,ll k,bool smaller) {
    // 途中だがkが0になった。(=残りの桁があっても、0で埋まるので1を返す)
    if (k == 0) return 1;

    // 最後の桁まで走査した(= 最後の桁まで決定した && k != 0 なので 0を返す)
    if ( i == N.size()) return 0;

    // N未満であることが確定しているならば残りの桁は何でも入るので組み合わせを使って返す
    if (smaller) return combination(N.size()-i,k) * (ll)pow((ll)9,(ll)k);

    // まだ未満とは限らない場合

    // 今見ている桁に相当するNの値が0なら先に進む。
    if (N[i] == '0') return solve(i+1,k,false);

    // N[i]が0でない場合、 その桁には0,1,...と入る可能性がある。
    // i桁目に0を入れた場合の個数 (明らかにN以下の値になるためフラグはtrueになる)
    auto zero = solve(i+1,k,true);
    // i桁目に0<k<N[i]を満たす様な値を入れた場合(明らかにN以下の値になるためフラグはtrueになる)
    // N[i] == 1ならmidはないし、N[i] == 3ならmidはN[i] == 1,2のことになるので適宜調整をする。
    auto mid =  solve(i+1,k-1,true) * (N[i]- '1');
    // i桁目にN[i]を入れた場合
    auto last = solve(i+1,k-1,false);

    return zero + mid + last;

}

int main() {

    cin >> N;

    cin >> K;


    cout << solve(0,K, false) << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Almost Everywhere Zero
User reud
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2896 Byte
Status AC
Exec Time 24 ms
Memory 23936 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 4
AC × 22
Set Name Test Cases
Sample sample_01, sample_02, sample_03, sample_04
All hand_01, hand_02, hand_03, hand_04, hand_05, max_01, max_02, max_03, max_04, max_05, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
hand_01 AC 1 ms 256 KB
hand_02 AC 1 ms 256 KB
hand_03 AC 24 ms 23936 KB
hand_04 AC 22 ms 23680 KB
hand_05 AC 23 ms 23680 KB
max_01 AC 23 ms 23680 KB
max_02 AC 23 ms 23680 KB
max_03 AC 22 ms 23680 KB
max_04 AC 23 ms 23680 KB
max_05 AC 23 ms 23680 KB
random_01 AC 24 ms 23680 KB
random_02 AC 23 ms 23680 KB
random_03 AC 22 ms 23680 KB
random_04 AC 22 ms 23680 KB
random_05 AC 23 ms 23680 KB
random_06 AC 23 ms 23680 KB
random_07 AC 24 ms 23680 KB
random_08 AC 23 ms 23680 KB
sample_01 AC 23 ms 23680 KB
sample_02 AC 23 ms 23680 KB
sample_03 AC 24 ms 23680 KB
sample_04 AC 23 ms 23680 KB