X Number

http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1006&cid=881
タイトル:
Lをあげて、R、d L、R、d L、R、d、求めて[L、R][L、R][L、R][L、R]の中で何個の数があって、10進数の位の上でd dが最も多い(厳格で最も多い)を満たします
解析:
移動後から10進数ビットを巡回し、c[i]c[i]c[i]は現在位置より前の数字i i iが出現した回数を維持する.
現在のビットは[0,H(上限)−1][0,H(上限)−1][0,H(上限)−1]を列挙し,次のビットは任意に選択できる.この場合のシナリオ数を考慮して解く.
次のd d dの回数を列挙すると,他の数の上限が得られ,指数型母関数により配列スキームを解くことができる.
次にd d d dがa d d addのadd回を選択したと仮定する.
∏ i ∈ [ 0 , 9 ] i ≠ d ( 1 + x + . . . x l i m i l i m i ! )\prod_{iin[0,9]}^{iot=d}(1+x+…dfrac{x^{lim_i}{lim_i!})∏i∈[0,9]i=d(1+x+...limi!xlimi)におけるx l e n−a d(l e n−a d)!dfrac{x^{len-add}}{(len-add)!} (len−add)!xlen−addの係数は他の数の配列スキーム数であり,さらにC l e n a d C_を乗じる.{len}^{add}Clenaddはd d dを計算します.
この係数はlenが小さいのでlong doubleで直接使えます.
面倒なのはトップ0の判断で、細部が多く、最後の1位以外の0はc c c配列に計上されず、この部分はdfsで上の部分に変換できる.
コード:

/*
 *  Author : Jk_Chen
 *    Date : 2020-07-28-10.02.53
 */
#include
using namespace std;
#define LL long long
#define LD long double
#define rep(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pill pair
#define fi first
#define se second
void test(){cerr<<"
";}
template<typename T,typename... Args>void test(T x,Args... args){cerr<<"> "<<x<<" ";test(args...);}
const LL mod=1e9+7;
const int maxn=1e5+9;
const int inf=0x3f3f3f3f;
LL rd(){ LL ans=0; char last=' ',ch=getchar();
    while(!(ch>='0' && ch<='9'))last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans; return ans;
}
#define rd rd()
/*_________________________________________________________begin*/

int c[10];
int d;
bool check(){
    int mx=-1;
    rep(i,0,9){
        mx=max(mx,c[i]);
    }
    if(c[d]!=mx)return 0;
    rep(i,0,9){
        if(i!=d && c[i]==mx)return 0;
    }
    return 1;
}
LD vec[20];
LD tmp[20];
LL fac[20];
LD invfac[20];
LL C(int n,int m){
    return fac[n]/fac[m]/fac[n-m];
}
LL cal(int reslen){
    if(reslen==0)return check();
    LL ans=0;
    rep(add_d,0,reslen){
        int lim[10];
        bool cant=0;
        int sumlim=0;

        rep(i,0,9){
            if(i==d)continue;
            lim[i]=c[d]+add_d-1-c[i];
            sumlim+=lim[i];
            if(lim[i]<0){
                cant=0;break;
            }
        }
        if(cant||sumlim+add_d<reslen)
            continue;

        mmm(vec,0);
        vec[0]=1;
        int up=reslen-add_d;
        rep(i,0,9){
            if(i==d)continue;
            mmm(tmp,0);
            rep(j,0,lim[i]){
                rep(k,0,up){
                    if(j+k>up)break;
                    tmp[j+k]+=vec[k]*invfac[j];
                }
            }
            rep(j,0,up)vec[j]=tmp[j];
        }
        LL part=(LL)round(vec[up]*(LD)fac[up]);
        ans+=part*C(reslen,add_d);
    }
    return ans;
}
LL cal0(int reslen){
    if(reslen==0)return check();
    LL ans=0;
    rep(i,1,9){
        c[i]++;
        ans+=cal(reslen-1);
        c[i]--;
    }
    if(reslen==1)
        c[0]++;
    ans+=cal0(reslen-1);
    return ans;
}
LL getAns(const char *x,int len,int p=1){
    if(p>len){
        return check();
    }
    LL ans=0;
    rep(i,1,x[p]-1){
        c[i]++;
        ans+=cal(len-p);
        c[i]--;
    }
    // 0...
    if(x[p]!=0){
        if(p==1){
            if(len==1){
                if(d==0)ans++;
            }
            else{
                ans+=cal0(len-p);
                mmm(c,0);
            }
        }
        else{
            c[0]++;
            ans+=cal(len-p);
            c[0]--;
        }
    }

    c[x[p]]++;
    ans+=getAns(x,len,p+1);
    return ans;
}

LL Prin(LL l,LL r){
    LL ans=0;
    for(LL i=l;i<=r;i++){
        mmm(c,0);
        LL tmp=i;
        while(tmp){
            c[tmp%10]++;
            tmp/=10;
        }
        if(check())ans++;//,test(i);
    }
    printf("real %lld
",ans);
}

int main(){
    invfac[0]=1;
    fac[0]=1;
    rep(i,1,18)
        invfac[i]=invfac[i-1]/i,
        fac[i]=fac[i-1]*i;
    int t=rd;
    while(t--){
        char x[30],y[30];
        int lx,ly;
#define TEST_
#ifdef TEST
        LL l=rd,r=rd;
        LL tmpl=l,tmpr=r;
        d=rd;
        lx=0,ly=0;
        while(l){
            x[++lx]=l%10;
            l/=10;
        }
        while(r){
            y[++ly]=r%10;
            r/=10;
        }
        reverse(x+1,x+1+lx);
        reverse(y+1,y+1+ly);
        l=tmpl,r=tmpr;

        Prin(l,r);

#else
        scanf("%s%s%d",x+1,y+1,&d);
        lx=strlen(x+1);
        ly=strlen(y+1);
        rep(i,1,lx)x[i]-='0';
        rep(i,1,ly)y[i]-='0';
        assert(!(lx>1&&x[1]==0));
        assert(!(ly>1&&y[1]==0));

#endif // TEST

        mmm(c,0);
        LL Ans=getAns(y,ly);
        mmm(c,0);
        Ans-=getAns(x,lx);
        mmm(c,0);
        rep(i,1,lx){
            c[x[i]]++;
        }
        if(check())Ans++;
        printf("%lld
",Ans);
    }
    return 0;
}