Submission #2036531

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define NDEBUG
#include "cout11.h"
#endif
#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

inline ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

const ll M=1000000007LL;

inline ll ADD(ll x, ll y) { return (x+y) % M; }
inline ll SUB(ll x, ll y) { return (x-y+M) % M; }
inline ll MUL(ll x, ll y) { return x*y % M; }
inline ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
inline ll DIV(ll x, ll y) { return MUL(x, POW(y, M-2)); }
// ll comb(ll n, ll k) { ll v=1; for(ll i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }

map<int, ll> _mm_tp;

inline ll tp(int k) {
    if (found(_mm_tp, k)) return _mm_tp[k];
    ll a = MUL(9, POW(10, k-1));
    _mm_tp[k] = a;
    return a;
}


// ax+by=gcd(a,b) を満たすx,yを1組求めたい時に
ll extgcd(ll a, ll b, ll &x, ll &y, ll c=1, ll d=0, ll e=0, ll f=1) {
  if (b == 0) {
    x = c; y = e;  // dot([c,d; e,f], [1;0])
    return a;
  }
  ll q = a/b, r = a%b;
  return extgcd(b, r, x, y, d, c-q*d, f, e-q*f);  // dot([c,d; e,f], [0,1; 1,-q])
}
/*
    int a = atoi(argv[1]), b = atoi(argv[2]);
    int x, y;
    int g = extgcd(a, b, x, y);
    printf("gcd(%d,%d)=%d; x=%d,y=%d\n", a, b, g, x, y);
*/

ll pat(ll k0, ll k1, int S, int xmin, int xmax, int ymin, int ymax) {
    ll g = gcd(k0, k1);
    // k0:0 k1:S/k1
    if (S % g) return 0;

    k0 /= g; k1 /= g; S /= g;

    ll x, y;
    extgcd(k0, k1, x, y); // -> 1
    // ll m = k0 * k1;
    // printf("extgcd(%lld, %lld) -> (%lld, %lld) x %lld\n", k0, k1, x, y, g);
    x *= S; y *= S;
    if (x < xmin) {
        ll m = (xmin - x + k1-1) / k1;

        x += k1 * m;
        y -= k0 * m;
    }
    assert(xmin <= x);

    if (x >= xmin + k1) {
        ll m = (x - xmin) / k1;
        x -= k1 * m;
        y += k0 * m;
    }
    assert(xmin <= x && x < xmin+k1);

    if (y < ymin) return 0;
    assert(ymin <= y);

    if (y > ymax) {
        ll m = (y - ymax + k0-1) / k0;
        x += k1 * m;
        y -= k0 * m;
    }
    assert(y <= ymax);

    if (xmax < x || y < ymin) return 0;
    assert(xmin <= x && x <= xmax);
    assert(ymin <= y && y <= ymax);

#if 0
    printf("x:%lld [%d .. %d], y:%lld [%d .. %d]\n", x,xmin,xmax, y,ymin,ymax);
#endif
    // x: ++
    // y: --
    ll m = min((xmax - x) / k1, (y - ymin) / k0);
    return 1LL + m;
}

ll solve(int S) {
    ll total = 0;

    for (int lo=1; lo<=min(10,S); ++lo) {
        // lo * (1..9x)
        if (S % lo == 0) {
            int u = S / lo;
            ll _tp = tp(lo);
            if (lo >= 10 || u <= _tp) {
                ll aug = SUB(_tp, u-1);
#if DEBUG
                if (aug > 0)
                    printf("[%d] +%lld\n", lo, aug);
#endif
                total += aug;
            }
        }

        // if (S / lo == 1) continue;

        for (int hi=lo+1; hi<=S; ++hi) {
            ll aug = 0, mid = 0;

            // a lo + [mid] + b hi = S;
            for (int k=lo+1; k<hi; ++k) {
                if (k > 9) { mid = -1; break; }
                mid += k * tp(k);
            }

            if (mid == -1 || lo+mid+hi > S) break;
            aug = pat(lo, hi, S - mid,
                         1, (lo < 9 ? tp(lo) : S),
                         1, (hi < 9 ? tp(hi) : S) );
#if DEBUG
            if (aug > 0) {
                printf("[%d .. %d] (mid=%lld) +%lld\n", lo, hi, mid, aug);
            }
#endif
            total = ADD(total, aug);
        }
    }

    int last_lo = S+1;

    for (int d=1; ; ++d) {
        int lo = S / d;
        if (lo <= 10) break;
        if (lo == last_lo) continue;
        last_lo = lo;

        // lo * (1..9x)
        if (S % lo == 0) {
            int u = S / lo;
            ll _tp = tp(lo);
            ll aug = SUB(_tp, u-1);
#if DEBUG
            if (aug > 0) {
                printf("[%d] +%lld\n", lo, aug);
            }
#endif
            total += aug;
        }
        {
            int hi = lo + 1;
            ll aug = pat(lo, hi, S,
                         1, (lo < 9 ? tp(lo) : S),
                         1, (hi < 9 ? tp(hi) : S) );
#if DEBUG
            if (aug > 0) {
                printf("[%d .. %d] +%lld\n", lo, hi, aug);
            }
#endif
            total = ADD(total, aug);
        }
    }
    return total % M;
}

int main() {
    int S; cin >> S;
    cout << solve(S) << endl;
    return 0;
}

Submission Info

Submission Time
Task F - Number of Digits
User naoya_t
Language C++14 (GCC 5.4.1)
Score 900
Code Size 5463 Byte
Status
Exec Time 34 ms
Memory 384 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
All 900 / 900 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
Case Name Status Exec Time Memory
01.txt 1 ms 256 KB
02.txt 1 ms 256 KB
03.txt 1 ms 256 KB
04.txt 1 ms 256 KB
05.txt 1 ms 256 KB
06.txt 31 ms 256 KB
07.txt 4 ms 256 KB
08.txt 30 ms 384 KB
09.txt 2 ms 256 KB
10.txt 27 ms 256 KB
11.txt 8 ms 256 KB
12.txt 7 ms 256 KB
13.txt 27 ms 256 KB
14.txt 19 ms 256 KB
15.txt 30 ms 256 KB
16.txt 4 ms 256 KB
17.txt 4 ms 256 KB
18.txt 4 ms 256 KB
19.txt 4 ms 256 KB
20.txt 4 ms 256 KB
21.txt 4 ms 256 KB
22.txt 4 ms 256 KB
23.txt 22 ms 256 KB
24.txt 22 ms 256 KB
25.txt 22 ms 256 KB
26.txt 12 ms 256 KB
27.txt 16 ms 256 KB
28.txt 26 ms 256 KB
29.txt 30 ms 256 KB
30.txt 23 ms 256 KB
31.txt 12 ms 256 KB
32.txt 30 ms 256 KB
33.txt 10 ms 256 KB
34.txt 34 ms 256 KB
35.txt 22 ms 256 KB
36.txt 26 ms 256 KB
37.txt 33 ms 256 KB
38.txt 15 ms 256 KB
39.txt 34 ms 256 KB
40.txt 16 ms 256 KB
41.txt 1 ms 256 KB
42.txt 22 ms 256 KB
43.txt 22 ms 256 KB
44.txt 22 ms 256 KB
45.txt 1 ms 256 KB
46.txt 4 ms 256 KB
47.txt 22 ms 256 KB
48.txt 1 ms 256 KB
49.txt 4 ms 256 KB
50.txt 22 ms 256 KB
51.txt 1 ms 256 KB
52.txt 1 ms 256 KB
53.txt 1 ms 256 KB
54.txt 2 ms 256 KB
55.txt 26 ms 256 KB
56.txt 34 ms 256 KB
57.txt 34 ms 256 KB
58.txt 34 ms 384 KB
59.txt 34 ms 256 KB
60.txt 16 ms 256 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB
sample-03.txt 1 ms 256 KB
sample-04.txt 1 ms 256 KB
sample-05.txt 1 ms 256 KB