2 条题解

  • 0
    @ 2025-10-8 17:01:53

    by hansang:

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=35;
    struct node{
        LL a[15], s;
        node(){s=0; memset(a, 0, sizeof(a));}
    }f[N][15]; LL a[N];
    node operator+(node n1, node n2){
        for(int i=0; i<=9; i++)
            n1.a[i]+=n2.a[i];
        n1.s+=n2.s; 
        return n1;
    }
    node operator-(node n1, node n2){
        for(int i=0; i<=9; i++)
            n1.a[i]-=n2.a[i];
        return n1;
    }
    node operator*(node no, LL x){
        for(int i=0; i<=9; i++)
            no.a[i]*=x;
        return no;
    }
    node calc(LL x){
        int len=0; node ans, sum;
        while(x>0) a[++len]=x%10, x/=10;
        for(int i=len; i>=1; i--){
            for(int j=(i==len)? 1: 0; j<a[i]; j++){
                ans=ans+f[i][j];
                ans=ans+sum*f[i][j].s;
            }
            sum.a[a[i]]++;
            if(i==1){
                for(int j=1; j<=len; j++){
                    ans.a[a[j]]++;
                }
            }
        }
        for(int i=len-1; i>=1; i--)
            for(int j=1; j<=9; j++){
                ans=ans+f[i][j];
            }
        return ans;
    }
    int main(){
        for(int i=0; i<=9; i++){
            f[1][i].a[i]=1;
            f[1][i].s=1;
        }
        for(int i=2; i<=30; i++)
            for(int j=0; j<=9; j++)
                for(int k=0; k<=9; k++){
                    f[i][j]=f[i][j]+f[i-1][j];
                    f[i][j].a[k]+=f[i-1][j].s;
                }
        LL a, b; scanf("%lld%lld", &a, &b);
        node no=calc(b)-calc(a-1);
        for(int i=0; i<=9; i++) printf("%lld ", no.a[i]);
        printf("\n");
        return 0;
    }
    
    • 0
      @ 2025-10-8 17:01:44

      by hansang:

      #include<bits/stdc++.h>
      using namespace std;
      typedef long long LL;
      const int N=35;
      struct node{
          LL a[15], s;
          node(){s=0; memset(a, 0, sizeof(a));}
      }f[N][15]; LL a[N];
      node operator+(node n1, node n2){
          for(int i=0; i<=9; i++)
              n1.a[i]+=n2.a[i];
          n1.s+=n2.s; 
          return n1;
      }
      node operator-(node n1, node n2){
          for(int i=0; i<=9; i++)
              n1.a[i]-=n2.a[i];
          return n1;
      }
      node operator*(node no, LL x){
          for(int i=0; i<=9; i++)
              no.a[i]*=x;
          return no;
      }
      node calc(LL x){
          int len=0; node ans, sum;
          while(x>0) a[++len]=x%10, x/=10;
          for(int i=len; i>=1; i--){
              for(int j=(i==len)? 1: 0; j<a[i]; j++){
                  ans=ans+f[i][j];
                  ans=ans+sum*f[i][j].s;
              }
              sum.a[a[i]]++;
              if(i==1){
                  for(int j=1; j<=len; j++){
                      ans.a[a[j]]++;
                  }
              }
          }
          for(int i=len-1; i>=1; i--)
              for(int j=1; j<=9; j++){
                  ans=ans+f[i][j];
              }
          return ans;
      }
      int main(){
          for(int i=0; i<=9; i++){
              f[1][i].a[i]=1;
              f[1][i].s=1;
          }
          for(int i=2; i<=30; i++)
              for(int j=0; j<=9; j++)
                  for(int k=0; k<=9; k++){
                      f[i][j]=f[i][j]+f[i-1][j];
                      f[i][j].a[k]+=f[i-1][j].s;
                  }
          LL a, b; scanf("%lld%lld", &a, &b);
          node no=calc(b)-calc(a-1);
          for(int i=0; i<=9; i++) printf("%lld ", no.a[i]);
          printf("\n");
          return 0;
      }
      • 1

      USACO(37)数位1:区间数字的个数[Dream Counting&#44; 2006 Dec]

      信息

      ID
      2634
      时间
      1000ms
      内存
      128MiB
      难度
      10
      标签
      递交数
      4
      已通过
      1
      上传者