2013-team5/andrew/30/D

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
const int INF=1e8, MN=1e6+7;
LL l,r,f[30],v[30];
LL C[40][40];

void comb(){
    C[0][0]=1;
    for (int i=1; i<=20; i++){
        C[i][0]=1;
        for (int j=1; j<i; j++)
            C[i][j]=C[i-1][j-1]+C[i-1][j];
        C[i][i]=1;
    }
}


LL A(int n,int m){
    LL ans=1;
    for (LL i=n-m+1; i<=n; i++) ans*=i;
    return ans;
}

LL calc(int k0){
    int i,j,k=k0,n=0,m=0;
    for (i=0; i<10; i++)
        if (v[i]>0){
            n++;
            m+=v[i]==2;
        }
    LL ans=0;
    for (i=0; i<=m && k>=0; i++,k-=2){
        LL tmp=A(n-i,k)*C[m][i];
        for (j=k+2; j<=k0; j+=2) tmp*=C[j][2];
        ans+=tmp;
    }
    return ans;
}

LL gao(LL s){
    if (s==0) return 0;
    LL w=s;
    int t[30]={};
    while (s){ t[++t[0]]=s%10; s/=10; }
    int i,j;
    LL ans=0;
    v[0]--;
    for (i=t[0]-1; i>=2; i--){
        ans+=calc(i-1)*9ll;
    }
    v[0]++;
    if (t[0]>1) ans+=9;
    for (i=t[0]; i>=1; i--){
        for (j=(i==t[0])?1:0; j<t[i]; j++) if (v[j]>0){
            v[j]--;
            ans+=calc(i-1);
            v[j]++;
        }
        if (--v[t[i]]<0) break;
    }
   /* int flag=1;
    for (i=1; i<=t[0]; i++)
        if (v[i]<0) flag=0;
    */

    int flag=1,h[20];
    memset(h,0,sizeof(h));
    while (w){ h[w%10]++; w/=10; }
    for (int j=0; j<10; j++)
        if (h[j]>2) flag=0;
    ans+=flag;
    return ans;
}

LL gao0(int n){
    int h[10],ans=0;
    for (int i=1; i<=n; i++){
        int t=i;
        memset(h,0,sizeof(h));
        while (t){ h[t%10]++; t/=10; }
        int flag=1;
        for (int j=0; j<10; j++)
            if (h[j]>2) flag=0;
        ans+=flag;
    }
    return ans;
}

int main(){
    freopen("exchange.in","r",stdin);
    freopen("exchange.out","w",stdout);
    scanf("%I64d%I64d",&l,&r);
    //cin >> l >> r ;
    comb();
    f[0]=1;
    for (int i=1; i<=18; i++) f[i]=f[i-1]*i;
    for (int i=0; i<10; i++) v[i]=2;
    LL a1=gao(r);
    for (int i=0; i<10; i++) v[i]=2;
    LL a2=gao(l-1);

    //cout << a1-a2 << endl;
    printf("%I64d\n",a1-a2);

    /*for (int j=500; j<=20000; j++){
        for (int i=0; i<10; i++) v[i]=2;
        if (gao(j)!=gao0(j)) cout << j<< endl;
    }
    for (int i=0; i<10; i++) v[i]=2;
*/


    //cout << gao(1000)-gao(0) << endl;


    //cout << a1-a2 << endl;
    //cout << gao(1e18) << endl;
    //cout << gao(555555) << endl;
    //cout << gao(125545555) << endl;
    //cout << gao0(125545555) << endl;
    return 0;
}
}}}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
const int INF=1e8, MN=1e6+7;
LL l,r,f[30],v[30];
LL C[40][40];
void comb(){
    C[0][0]=1;
    for (int i=1; i<=20; i++){
        C[i][0]=1;
        for (int j=1; j<i; j++)
            C[i][j]=C[i-1][j-1]+C[i-1][j];
        C[i][i]=1;
    }
}
LL A(int n,int m){
    LL ans=1;
    for (LL i=n-m+1; i<=n; i++) ans*=i;
    return ans;
}
LL calc(int k0){
    int i,j,k=k0,n=0,m=0;
    for (i=0; i<10; i++)
        if (v[i]>0){
            n++;
            m+=v[i]==2;
        }
    LL ans=0;
    for (i=0; i<=m && k>=0; i++,k-=2){
        LL tmp=A(n-i,k)*C[m][i];
        for (j=k+2; j<=k0; j+=2) tmp*=C[j][2];
        ans+=tmp;
    }
    return ans;
}
LL gao(LL s){
    if (s==0) return 0;
    LL w=s;
    int t[30]={};
    while (s){ t[++t[0]]=s%10; s/=10; }
    int i,j;
    LL ans=0;
    v[0]--;
    for (i=t[0]-1; i>=2; i--){
        ans+=calc(i-1)*9ll;
    }
    v[0]++;
    if (t[0]>1) ans+=9;
    for (i=t[0]; i>=1; i--){
        for (j=(i==t[0])?1:0; j<t[i]; j++) if (v[j]>0){
            v[j]--;
            ans+=calc(i-1);
            v[j]++;
        }
        if (--v[t[i]]<0) break;
    }
   /* int flag=1;
    for (i=1; i<=t[0]; i++)
        if (v[i]<0) flag=0;
    */
    int flag=1,h[20];
    memset(h,0,sizeof(h));
    while (w){ h[w%10]++; w/=10; }
    for (int j=0; j<10; j++)
        if (h[j]>2) flag=0;
    ans+=flag;
    return ans;
}
LL gao0(int n){
    int h[10],ans=0;
    for (int i=1; i<=n; i++){
        int t=i;
        memset(h,0,sizeof(h));
        while (t){ h[t%10]++; t/=10; }
        int flag=1;
        for (int j=0; j<10; j++)
            if (h[j]>2) flag=0;
        ans+=flag;
    }
    return ans;
}
int main(){
    freopen("exchange.in","r",stdin);
    freopen("exchange.out","w",stdout);
    scanf("%I64d%I64d",&l,&r);
    //cin >> l >> r ;
    comb();
    f[0]=1;
    for (int i=1; i<=18; i++) f[i]=f[i-1]*i;
    for (int i=0; i<10; i++) v[i]=2;
    LL a1=gao(r);
    for (int i=0; i<10; i++) v[i]=2;
    LL a2=gao(l-1);
    //cout << a1-a2 << endl;
    printf("%I64d\n",a1-a2);
    /*for (int j=500; j<=20000; j++){
        for (int i=0; i<10; i++) v[i]=2;
        if (gao(j)!=gao0(j)) cout << j<< endl;
    }
    for (int i=0; i<10; i++) v[i]=2;
*/
    //cout << gao(1000)-gao(0) << endl;
    //cout << a1-a2 << endl;
    //cout << gao(1e18) << endl;
    //cout << gao(555555) << endl;
    //cout << gao(125545555) << endl;
    //cout << gao0(125545555) << endl;
    return 0;
}