Educational Codeforces Round 50 (Rated for Div. 2) C. Classy Numbers

C. Classy Numbers

题目链接：https://codeforces.com/contest/1036/problem/C

题意：

给出n个询问，每个询问给出L,R，问在这个闭区间中有多少个数满足，除开0之外，最多只有4个数字。

题解：

由于题目给出的数满足前缀性质，所以我们可以直接求[1,r]这个区间中有多少个数满足就好了。

具体做法就是从高位往低位来看，然后如果当前数组不为0，假设为p，那么当前数组对答案的贡献就比较好计算了，假设后面的数有x位，目前已经有k个数字了。

那么分两种情况：一种是当前这位为0的时候，那么贡献就是C(x,3-k)；另外一种就是当前这位为1~p-1的时候，贡献就是(p-1)*C(x,3-k-1)。

当前为p的情况我们留在后面统计就行了，因为这种情况主要是取决后面的数的。

细节见代码吧：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll C[][];

int T;

ll a,b;

int num[],pow9[]={,,,};

ll calc(ll x,ll k){

    ll ans = ;

    if(x<=) return ;

    for(int i=;i<=k;i++) ans+=C[x][i]*pow9[i];

    return ans ;

}

ll solve(ll x){

    memset(num,,sizeof(num));

    int n;

    for(n=;x;n++){

        num[n]=x%;

        x/=;

    }

    n--;

    ll ans = ;

    for(int i=n,cur=;i>=;i--){

        if(!num[i]) continue ;

        ans+=calc(i-,cur);

        cur--;

        ans+=(num[i]-)*calc(i-,cur);

        if(cur==) break ;

        //if(i==1) ans++;

    }

    return ans ;

}

int main(){

    ios::sync_with_stdio(false);cin.tie();

    C[][]=;C[][]=;

    for(int i=;i<=;i++){

        C[i][]=;

        for(int j=;j<=i;j++){

            C[i][j]=C[i-][j]+C[i-][j-];

        }

    }

    cin>>T;

    while(T--){

        cin>>a>>b;

        //cout<<solve(b)<<" "<<solve(a-1)<< '\n';

        cout<<solve(b)-solve(a-)<< '\n';

    }

    return ;

}