v.cpp

Bài toán

Độ phức tạp

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#define long long long

long K, A, B;

char sPossible[123];

bool bPossible[123];

char AA[123];

char BB[123];

bool ok(long x){

    while (x) {

        if (!bPossible[x%10]) return false;

        x/=10;

    }

    return true;

}

long first(){

    long r=0;

    long head = A/K*K; while (head<A) head+=K;

    for (long i=head; i<=B; i+=K)

    if (ok(i)) r++;

    return r;

}

long F[13][102309][2][2][2];

int FF[13][102309][2][2][2];

#define current_state pos][current][smaller][bigger][one

long f(int pos, int current, bool smaller, bool bigger, bool one){

    if (AA[pos]==0)

        if (current==0) return 1;

        else return 0;

    if (FF[current_state]++) return F[current_state];

    long r=0;

    for (int i=0; i<=9; i++)

    if (bPossible[i] || (i==0 && !one))

    if (smaller || i<=BB[pos]-'0')

    if (bigger || i>=AA[pos]-'0')

    r += f(pos+1, (current*10+i)%K, smaller || i<BB[pos]-'0', bigger || i>AA[pos]-'0', one || i);

    //printf("f(%d, %d, %d, %d, %d) = %d\n", pos, current, (int)smaller, (int)bigger, (int)one, r);

    return F[current_state]=r;

}

main(){

    int i;

    scanf("%lld%lld%lld", &K, &A, &B);

    scanf("%s", sPossible);

    for (i=0; sPossible[i]; i++) bPossible[sPossible[i]-'0']=true;

    if ((B-A)/K<=1230997)

        printf("%lld\n", first());

    else {

        sprintf(AA, "%012lld", A);

        sprintf(BB, "%012lld", B);

        //printf("%s\n%s\n", AA, BB);

        printf("%lld\n", f(0,0,0,0,0));

    }

}

Nhận xét